読者です 読者をやめる 読者になる 読者になる

pekempeyのブログ

競技プログラミングに関する話題を書いていきます。

Codeforces Good Bye 2015 D. New Year and Ancient Prophecy

動的計画法 Codeforces Suffix Array Rolling Hash

問題文

http://codeforces.com/contest/611/problem/D

解法

この問題では次のような DP がうまくいく。

  • dp[i][j] := 最後に作った数が [i, i+j) であるような分割のパターン数

数の大小判定は、

  1. 桁数の大小比較をする
  2. 桁数が等しいなら、辞書順比較をする

の 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 ...

SA を発見するまでは良かったものの通すことができず残念。 SA と LCP をよく知らないので後で勉強しておこう。