pekempeyのブログ

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

Codeforces Manthan, Codefest 16 C. Spy Syndrome 2

制約が怖すぎる。

codeforces.com

解法

次のような DP をしたあとで復元する。

  • dp[i] := 先頭 i 文字に単語を割り当てられる

S[i..j] が単語のリストにあれば dp[i] から dp[j+1] に遷移できる。 状態数が 10000、遷移数が 1000 なので厳しそうだけど通る。

多項式ハッシュを使えば単語リストにあるかの判定をO(1) あるいは O(log n) でできる。 ただし最大単語数が 105 個なので一種類のハッシュでは高確率でハッシュが衝突することに注意する必要がある(誕生日のパラドックス)。

Codeforces Manthan, Codefest 16 C. Spy Syndrome 2

ハッシュの計算がおかしかったので衝突や TLE 以前に WA だった。 それにしても制約が厳しい。