504.1

鯖落ち。外れセットだったのでまぁいいか、という感じ。

250

見てない。

500

文字の二次元配列が与えられて、隣り合う二文字のパターンで更新をしていく。最終的なパターンが与えられるので、可能な初期配置は何通りか答えよ、という問題。

更新処理を行単位でやって、固定文字に変更された部分は出力と一致していれば元がなにであっても良く、そうでないものは出力と同じものが入力にきていないとダメ、というだけの問題。

1000

文字列について、順番にスタックに積んでいくが、Bを読んだら次の文字を別のスタックに積み、Cを呼んだら二つのスタックを吐き出す、という処理をする。このときに吐き出された文字列が与えられるので、元の文字列は何通り可能か答えよ、という問題。Cの数は高々K個とする。

出力の部分文字列について、Cで挟まれていると思えば、それを出力可能かどうかが分かれば、後は単純なDPになる。(Cの出てきた回数と出力した文字長を状態に何通りか覚えておくだけ。)出力可能かどうかは、Bの数とBの直後にCがいるかどうかで、二つ目のスタックに入っていた文字の数が分かるので、Bの周辺の文字が復元できる。さらに一つ目のスタックに入っていた文字から全体が復元できる。うまくいく方法が何通りあるか調べれば良さそう。実装がかなり面倒そう...。