316.1

保留のヤツの続き。

900

移動を意味する文字列が与えられる。各移動について先頭から順に、それに従うかどうかを選択でき、ゴールを目指す。盤面が与えられるので、相手よりも早く先にゴールできるような文字列にしたい。このとき、先頭から何文字を削ればそのような文字列にできるか求めよ、という問題。

ある文字でゴールできると仮定したときに、どの文字から始まっているとゴールできるかについて考える。このときの相手側の先頭の文字を落としてしまえば、その文字でゴールすることはできなくなり、かつ自分がゴールできればそれが最適。このようなケースがなければ次の文字について考える。ゴールできるかどうかの状態は探索で、メモしてやれば毎回盤面を一度調べる程度。メモリ利用量が若干多いので、適当に圧縮してやる必要があるかも。(この手の先頭を知りたい問題は取り敢えず尻尾を捕まえるとうまくいくことが結構ある気がする。)

ちなみに、ゴールする文字が後ろになれば、相手がゴールできる先頭の文字の位置は広義単調増加になる。(後ろの命令を無視してもいいので、ゴールして待機というのができる。)なのでその分文字列を削らなくてはならなくなり、条件を満たすものがあったとしても最適ではなくなる。