C - chokudai Editorial by sugarrr
動的計画法(DP)を用います。
\(dp[i][j]\) を、「 \(S\) の \(i\) 文字目までを使って、chokudai の \(j\) 文字目まで選択する方法」と定義します。
ここで、\(N=|S|\) , \(T= \)chokudai として、以下の漸化式が成り立ちます。
\(\displaystyle dp[i][j] = \begin{cases} 1 & ( j = 0) \\0 & ( i=0 , 1 \leq j \leq 8) \\dp[i-1][j]& ( 1 \leq i \leq N , 1\leq j \leq 8, S[i] \neq T[j] ) \\dp[i-1][j] + dp[i-1][j-1] & (1 \leq i \leq N , 1\leq j \leq 8, S[i] = T[j])\end{cases}\)
なぜ漸化式が成り立つのか分からない
\(j=0\) のとき
「chokudaiの \(0\) 文字目まで選択する」というのは、下線を全く引いていないことを表します。つまり \(1\) 通りです。\( i=0 , 1 \leq j \leq 8\) のとき
「 \(S\) の \(0\) 文字目までを使う」すなわち「 \(S\) からまだ \(1\) 文字も使っていない」時に、「chokudaiの \(j (j \geq 1)\) 文字目まで選択する」ことはできません。つまり \(0\) 通りです。\(1 \leq i \leq N , 1\leq j \leq 8\) のとき
\(S[i] \neq T[j]\) のとき
「 \(S\) の \(i\) 文字目までを使って、\(T\) の \(j\) 文字目まで選択する方法」を考えていますが、\(S\) の \(i\) 文字目と \(T\) の \(j\) 文字目が異なるので、\(S\) の \(i\) 文字目に下線を引くことはありえません。よって「 \(S\) の \((i-1)\) 文字目までを使って、\(T\) の \(j\) 文字目まで選択する方法」の場合の数と等しいです。つまり \(dp[i-1][j]\) 通りです。\(S[i] = T[j]\) のとき
\(S\) の \(i\) 文字目に下線を引かない時
先程の議論から、これは \(dp[i-1][j]\) 通りです。\(S\) の \(i\) 文字目に下線を引く時
これは、「 \(S\) の \((i-1)\) 文字目までを使って、\(T\) の \((j-1)\) 文字目まで選択する方法」の場合の数と等しいです。つまり \(dp[i-1][j-1]\) 通りです。
まとめると、\(dp[i-1][j] + dp[i-1][j-1]\) 通りです。
for文の \(2\) 重ループを用いて、\(i, j\) が小さい順に \(dp[i][j]\) を全て求めることができます。
最終的な答えは \(dp[N][8]\) です。
このアルゴリズムの計算量は \(O(N)\) で、十分高速です。
posted:
last update: