AtCoder Beginner Contest 249 E問題 RLE - Kazun の競プロ記録

問題

atcoder.jp

提出解答

(※ 解説と動的計画法の添字の順番が逆になっている) atcoder.jp

問題の概要

文字列 $X$ に対して, 以下の方法で生成される文字列を $\operatorname{RLE}(X)$ *1 と書くことにする.

を以下を満たすように連続する部分列で分割する.
- 各部分列にある文字は全て同じである. つまり, ただ1つの文字からなっている.
- 分割したとき, 各部分列は極大である.
各部分列において, $\alpha$ が $k$ 個からなる文字列であるとき, その部分列を $\alpha k$ に置き換える (例: ${\tt aaa} \to {\tt a3}, {\tt bbbbbbbbbb} \to {\tt b10})$ .
順序を保ちながら, 文字列を連結させる.

以下を全て満たす文字列 $S$ の数を $P$ で割った余りを求めよ.

$S$ は英小文字からなる長さ $N$ の文字列
$|\operatorname{RLE}(S)| \lt N$

制約

$1 \leq N \leq 3000$
$10^8 \leq P \leq 10^9$
$P$ は素数

解法

動的計画法で解くことにする. $0 \leq i,j$ に対して, ${\rm DP}[i,j]$ を

$|S|=i, |\operatorname{RLE}(S)|=j$ となる文字列 $S$ の数

とする. このとき, 最終解答は

$\displaystyle \sum_{j=0}^{N-1} {\rm DP}[N, j]$

である.

ベースケースは $i=0$ のときで,

${\rm DP}[0,j]=[j=0]=\begin{cases} 1 & (j=0) \\ 0 & (j \gt 0) \end{cases}$

である.

更新式について, 整数 $t$ の桁数を $\operatorname{digit}(t)$ , 及び, 英小文字の種類数を $\sigma=26$ としたとき, ${\rm DP}[i,j]$ を求める際, $S$ の $i$ 文字目と何文字続いているかによって場合分けすることにより,

$\displaystyle {\rm DP}[i,j]=(\sigma-1)\sum_{t=1}^{j-1} {\rm DP}[i-t, j-(\operatorname{digit}(t)+1)]+\sigma {\rm DP}[0,j-(\operatorname{digit}(i)+1)]$

となる. なお, 計算のしやすさのために,

$\displaystyle X(i,j):=\sum_{t=1}^j {\rm DP}[i-t, j-(\operatorname{digit}(t)+1)]$

とおく. このとき, ${\rm DP}[i,j]=(\sigma-1)X(i,j)+{\rm DP}[0,j-(\operatorname{digit}(i)+1)$ ] である.

$X(i,j)$ を求める仮定について, $\operatorname{digit}(t)$ の値で分けることにより, $N \leq 3000$ という制約から,

$\displaystyle \begin{align} &\phantom{=}X(i,j)\\ &=\sum_{t=1}^9 {\rm DP}[i-t, j-2]+\sum_{t=10}^{99} {\rm DP}[i-t, j-3]+\sum_{t=100}^{999} {\rm DP}[i-t, j-4]+\sum_{t=1000}^{3000} {\rm DP}[i-t, j-5] \end{align}$

である ( $i \lt 0$ または $j \lt 0$ に対して, ${\rm DP}[i,j]=0$ とする).

そして, $X(i,j-1), X(i,j)$ の差分を見ると,

$\begin{align} &\phantom{=}X(i,j+1)-X(i,j) \\ &=({\rm DP}[i-1,j-2]+{\rm DP}[i-10, j-3]+{\rm DP}[i-100, j-4]+{\rm DP}[i-1000, j-5]) \\ &\phantom{==}-({\rm DP}[i-10,j-2]+{\rm DP}[i-100, j-3]+{\rm DP}[i-1000, j-4]) \end{align}$