392.1

もうちょっとなんだけどなぁ...。取り敢えず1000に時間が割けるセットが続いているのはいい兆候かも。

250

二つの文字列の中にワイルドカードが1文字ずつあるので、それぞれ任意の文字列に置き換えたときに、一致するかどうか答えよという問題。一致するときは最小の一致する文字列を答える。

先頭と尻尾からワイルドカードまで比較して、一致しなければダメ。一致したなら、うまくいくので、中身をうまく調整。オーバーラップする長さはせいぜい50通りくらいしかないので全部試す...という実装系かと思いきや。

賢い人は、ワイルドカードを固定長(*->?)にして、N文字のときにうまくいくのはあるかどうかを一通り試していた。こうすると二つの文字列が同じ長さになって、それぞれの同じ場所を比較すればいいだけなので、コードもすっきり。

500

1からNまでの状態があって、そのうちの状態Kから、Kの各桁の数の和だけ進んだ状態に移動する。Nの次は1とする。このとき、同じ状態に到達するまでのパスで最長のものを答えよという問題。

メモしながら一通り試すだけ。何のひっかけもなかった感じ。

1000

N以上の数のうち、各桁の数字の出現回数が等しいものの中で最小のものを答えよという問題。

数字の種類は2の10乗通りしかないので全部試す。同じ桁数になるまで各数字を使う回数を増やせば良い。後は、先頭から順に一番小さい数字を割り当てて、うまくいかないなら次に大きい数字を割り当てて...とやればいい。

N以上なので桁数は増えないのに、Nより大きいだと思っていた。後はN以上の最小のものを探すルーチンでバックトラックしなかったので、ある数字を使い切った時点で諦めていたという間違い...。もったいない。