Codeforces Good Bye 2015 D. New Year and Ancient Prophecy
問題文
http://codeforces.com/contest/611/problem/D
解法
この問題では次のような DP がうまくいく。
- dp[i][j] := 最後に作った数が [i, i+j) であるような分割のパターン数
数の大小判定は、
- 桁数の大小比較をする
- 桁数が等しいなら、辞書順比較をする
の 2 段階で行える。したがって、最後に作った数が j 桁なら、次に j+1 桁以上の数を作れば確実に単調増加の条件を満たす。つまり dp[i][j] から dp[i+j][j+1]~dp[i+j][∞] に遷移できる。一方 dp[i][j] から dp[i+j][j] に遷移できるのは、辞書順で [i, i+j) < [i+j, i+2j) のときのみである。
では、
- 遷移先が複数ある場合の対処
- 文字列の辞書順比較
はどうすればいいだろうか。
遷移先が複数ある場合の対処
imos 法を用いる。 具体的には dp[i+j][j+1]~dp[i+j][∞] に dp[i][j] を加算するのではなく、dp[i+j][j+1] に dp[i][j] を加算し、適当なタイミングで累積和を取る。
文字列の辞書順比較
愚直な比較は O(n) 掛かるケースがあると辛い。
そこで、接尾辞配列 (SA: Suffix Array) と Rolling Hash を持ち出す。これなら O(1) で比較できる。 SA とは、文字列 S の接尾辞全部をソートした配列のこと。
たとえば S="mississippi" であれば接尾辞をすべて列挙して
0 - mississippi 1 - ississippi 2 - ssissippi 3 - sissippi 4 - issippi 5 - ssippi 6 - sippi 7 - ippi 8 - ppi 9 - pi 10 - i
ソートすると、
10 - i 7 - ippi 4 - issippi 1 - ississippi 0 - mississippi 9 - pi 8 - ppi 6 - sippi 3 - sissippi 5 - ssippi 2 - ssissippi
なので、SA は [10, 7, 4, 1, 0, 9, 8, 6, 3, 5, 2] である。 ちなみに、文字列ではなく開始位置で管理する。
SA を使えば部分文字列同士の大小比較ができる。たとえば 123434 という文字列が与えられ、123 と 434 の辞書順比較がしたかったとする。このとき 123≠434 なら 123 と 434 の大小関係は 123434 と 434 の大小関係と同じなので、SA 上で 123434 と 434 の出現位置を見れば大小比較ができる。
0 - 123434 1 - 23434 4 - 34 2 - 3434 5 - 4 3 - 434
123434 は 0 番目で、434 は 5 番目なので 123434 < 434。
SA の実装については O(n log2 n) のアルゴリズムが蟻本に書いてあるが、 愚直に接尾辞全部を列挙してソートしても間に合うかもしれない。
123≠434 の判定は Rolling Hash を使えばいい。
Codeforces Good Bye 2015 D. New Year and Ancient P ...