298.1

500よりも簡単な1000でした。これは良問だと思う。(500で出てていいと思うけど。)

1000

文字列が三つ与えられるので、それぞれから適当に文字を除去して、全部が同じ空でない文字列になるようにするとき、最終的にできる文字列は何種類あるか答えよ、という問題。

使える文字は26文字で、空文字列から開始して、もし作れるのなら、次に26文字のうちいずれかを追加していけば、可能なものがすべて生成できる。後ろに付くものには同じ規則が成立するので、各文字列について既に使った文字数を覚えておいて、メモ付き探索をする。現在の三つの文字列の開始位置が分かっていれば、次に使う文字として可能な26文字すべてについて、どこに出現するかを計算することができる。(当然ながら必要な文字が出てくる最初の位置から計算していくのが最良。)最後に空文字列を除去するのと、各ステップが存在すれば1個カウントするのを忘れなければ問題なく動くはず。