ツバサの備忘録

主に備忘録代わりに精進記録を載せていくつもりです。

Good Bye 2015 D. New Year and Ancient Prophecy

Z algorithm

問題
 提出コード
$dp[l][r] = [l,r)$ の文字列を一つの年として見た時の、 $[l,n)$ の組み合わせの個数
とします。
$[l,r)$ の文字列を使用した、と言うことは、次に選ぶ $[r,x)$ が $[l,r)$ より真に大きい値になる必要があります。
条件は以下の二つで、どちらか片方を満たせばよいです。

$r-l \lt x-r$
これは、桁がそもそも大きいパターンです。
$r-l = x-r$ かつ、2つの文字列を左から順に見ていった場合に初めて異なる値を $[l,r)$ については $a$ 、 $[r,x)$ については $b$ としたときに、 $a \lt b$
桁が同じ場合です。

1つめのパターンはすぐに計算できます。2つめのパターンが含まれるか含まれないか、を調べればよいです。
これは、 $[l,n)$ についてZ algorithmを適用し、 $r$ からの接頭辞がどれだけ一致しているかを見ればよいです。
結局遷移は以下のようになります。

$r-l = x-r$ となる $x$ が含まれる場合
$\displaystyle dp[l][r] = \sum_{i = x}^{n}dp[r][i]$
含まれない場合
$\displaystyle dp[l][r] = \sum_{i = x + 1}^{n}dp[r][i]$

で計算できます。
累積和を更新しながらDPをすることで、 $O(N^{2})$ で解けます。