302.1

解ける気配の全くしない900はどうしたものか。

250

ある整数Nから1とNを除くNの約数Kについて、N+Kへの移動が1ステップでできる。このとき、整数Nから整数Mまでに移動する最小ステップ数を答えよ、という問題。

NとMは高々100kなので、約数を全部カウントしても1k個もない。後はBFSするだけ。250でBFSというのはこの時代としてはどうなんだろうという気もするけれど。

500

回文となる整数のうちK番目を答えよ、という問題。

2N+1桁の回文の数と2N+2桁の回文の数は等しいのに注意すれば、N桁の回文の数は、(N+1)/2桁の整数の数に等しいし、順番もその整数の順。(後ろは反転して付け足すだけ。奇数長なら真ん中一桁を除去する。)

900

文字列が複数個与えられるので、それらすべてを部分文字列として含む文字列のうち、最短かつ辞書順で先頭のものを答えよ、という問題。

K個使ってできる最短の文字列からK+1個使ってできる最短の文字列を作るDPはダメらしい。900と称するからにはこれで通るべきだと思ったが...。全探索+枝狩りは終わる気配がなかった。今思うとダイクストラすれば良かったんじゃないかなぁ...。

ダイクストラだと信じてリトライ。良く考えるとそこまで真面目に状態遷移を考慮する必要がないことが分かった。使った文字列の数は単調に増えていくので、より少ない方を先に計算してしまえばいい。(ていうかこれDPだ。)

DPの前処理として、他の文字列の部分文字列になっているものは除去することが大事。これにより、文字列の結合方向が後ろ側だけに限定できることと、必ず文字数が増える形での結合しか起こらないことが保障できる。(最初のDPはこれをやっていなかったので双方向に伸びてしまい、まずいことになった。直前に使った文字列を覚えておくことでこの問題は解決できる。)

ある文字列を後ろに追加するには、直前に使った文字列とできるだけオーバラップさせて配置するのが良い。(これは次の文字列が今の文字列を含まない場合に限り、正当である、と思う。)後は最短でかつ辞書順で先頭のものを、既に使った文字列集合と最後に使った文字列について覚えておけば良くて、全部使い終わった時点で最適なものを答えておけばいい。

オーバラップ判定の式が繰り返し呼び出されるようなので、それだけメモしておく必要がある。高速な最大オーバラップ判定は思い付かないので保留。きっと賢いアルゴリズムがあるはず。