238.1

特殊な知識は必要としないスタンダードなセット。BFSは使うけど。

200

使用した回数で出力する文字が決まっている機械が複数ある。連続使用回数と機械の番号が与えられるので、出力される文字列全体を答えよ、という問題。

単純にシミュレーションするだけ。

500

決定性有限オートマトンで、各状態から4つの入力に対しての遷移がそれぞれ与えられる。初期状態が不明のとき、ある特定の状態に収束させるのに必要な最小入力数を答えよ、という問題。

現在の状態として可能なものの集合を、新たな状態として持つ決定性有限オートマトンを作って、可能な状態を全探索。一番少ない回数で到達できる、可能な状態が一つからなる状態が求めるものなので、BFSすればおしまい。

1000

文字列集合Sをa{la,ua}(aがla個以上ua個以下連続するもの)b{lb,ub}c{lc,uc}d{ld,ud}と定義するとき、Sの任意の要素二つの組からなる集合の要素数を求めよ、という問題。

先頭側をs1、末尾側をs2として考えると、s1がaを含むかどうか、...、s2がdを含むかどうかの2^8通りに分けて考えることができる。laが0でなければ必ずaを含むことになる、とか、状態10000***は状態00001***と等価なので再度考える必要がないとかに注意。一番問題になるのは状態10001***のケースで、laが0になり得る場合はlaからuaまでは00001***の状態で計算済みなので、ua+1から2uaまでをカウントし、そうでない場合は2laから2uaまでをカウントするという点に注意する必要がある。

ロジカルに正しいかどうか検討していないけれど、正解はもっと単純な方式で出るっぽい。想定解もそっちだけれど、なぜうまくいくのか検討するのにかかる時間が尋常じゃなさそうだったので、保留。