[AtCoder] AGC 037 A – Dividing a String
問題
方針
下記の方針は間違いを含んでいるので追記を見てください。
文字列 \( S \) の部分文字列に、それぞれの隣接する部分文字列が異なるように分割したときの最大値を求めます。このとき、部分文字列は最長でも \( 2 \) であることが分かります。例えば、\(S = aaaa \) のとき、分割の仕方は、\( a, aa, a \) となります。
ここで、次の動的計画法を考えます。配列 \( d_1 (i) \) を \( i \) 文字目が一文字として分割されるときの分割数の最大値であり、\( d_2(i) \) を\( i \) 文字目がその前の文字と連結されるときの分割数の最大値とします。ここで、\( S \) の長さが \( 2 \) 以上のときを考えます。
また、\( i \) 文字目を \( c_i \) と表すことにします。
\( c_1 = c_2 \) のとき
初期値は、\(d_1(1) = 1\), \( d_1(2) = 1 \), \( d_2(1) = 0\), \( d_2(1) = 1\) となります。
\( c_1 \neq c_2 \) のとき
初期値は、\(d_1(1) = 1\), \( d_1(2) = 2 \), \( d_2(1) = 0\), \( d_2(1) = 1\) となります。
\( i \geq 3 \) のとき
配列の更新式は、
\( c_i = c_{i-1} \)のとき
コメントの指摘により訂正します。
\[\begin{eqnarray}
d_1(i) &=& d_2(i-1) + 1\\
d_2(i) &=& d_1(i-2) + 1
\end{eqnarray}\]
\(d_2(i) = d_1(i-1) + 1\) を \(d_2(i) = d_1(i-2) + 1\) に修正しました。
\( c_i \neq c_{i-1} \) のとき
\[\begin{eqnarray}
d_1(i) &=& d_1(i-1) + 1\\
d_2(i) &=& d_1(i-2) + 1
\end{eqnarray}\]
となります。どのような考えでこの式が導出されるかと言うと、\( c_i = c_{i-1} \) のときは、\( c_i \) を一文字として分割するときは、\( c_{i-2}c_{i-1} \) という部分文字列で分割されている必要があります。一方で、\( c_{i-1}c_{i} \) という文字に分割するときは、\( c_{i-2} \) という部分文字列で分割されている必要があります。
追記
コメントの初期値の指摘から再度問題を考えてみました。結論として公式の解説にある動的計画法の遷移に至りました。
前提として、部分文字列の長さは最大でも \( 2 \) であることと、長さが \( 2 \) の部分文字列が連続して分割されることはありません。例えば、\( S = c_1c_2c_3c_4 \) は少なくとも、\( c_1, \ c_2c_3,\ c_4 \) と分割でき、\( S = c_1c_2c_3c_4c_5 \) では、\( c_1c_2, \ c_3, \ c_4c_5 \) と分割できます。
長さが \( 2 \) の部分文字列が連続して分割されると、長さが \( 4 \) の文字列の分割の場合、"aa, aa" と分割する可能性があるので不適であることが分かります。
ここで、配列 \( d \) について \( d_i \) を \( i \) 文字目まで見た時の分割の最大値とします。
\( c_{i – 1} = c_{i} \) のとき
\(\cdots c_{i-3}c_{i-2}c_{i-1}c_{i} \) という文字列は、\( \cdots c_{i-3}, \ c_{i-2}, \ c_{i-1}c_{i} \) または、\( \cdots c_{i-3}, \ c_{i-2}\ c_{i-1}, \ c_{i} \) と分割されている必要があるので、
\[d_i = d_{i – 3} + 2\]
と更新されます。\( i – 3 \) 文字目までの分割から、\( 2 \) 増えるということですね。
\( c_{i – 1} \neq c_{i} \) のとき
\(\cdots c_{i-2}c_{i-1}c_{i} \) という文字列は、\( \cdots c_{i-2}c_{i – 1}, c_{i} \) と分割できるので、
\[d_i = d_{i – 1} + 1\]
と更新されます。\( \cdots c_{i-2}c_{i – 1}\)という部分はそれまでの計算によて最適に分割されています。
コード
修正前
#include <bits/stdc++.h> using namespace std; typedef long long ll; int main() { string S; cin >> S; set<string> s; int n = S.length(); if (n == 1) { cout << "1\n"; return 0; } if (n == 2) { if (S[0] == S[1]) { cout << "1\n"; } else { cout << "2\n"; } return 0; } int dp[n + 1][2]{}; dp[0][0] = 1; dp[0][1] = 0; if (S[0] == S[1]) { dp[1][0] = 1; dp[1][1] = 1; } else { dp[1][0] = 2; dp[1][1] = 1; } for (int i = 2; i < n; i++) { if(S[i] != S[i - 1]) { dp[i][0] = dp[i - 1][0] + 1; dp[i][1] = dp[i - 2][0] + 1; } else { dp[i][0] = dp[i - 1][1] + 1; dp[i][1] = dp[i - 2][0] + 1; } } cout << max(dp[n -1][0], dp[n - 1][1]) << "\n"; return 0; }
修正後
#include <bits/stdc++.h> using namespace std; typedef long long ll; int main() { string S; cin >> S; set<string> s; int n = S.length(); if (n == 1) { cout << "1\n"; return 0; } if (n == 2) { if (S[0] == S[1]) { cout << "1\n"; } else { cout << "2\n"; } return 0; } int dp[n]{}; // 1文字目 dp[0] = 1; // 2文字目 if (S[0] == S[1]) { dp[1] = 1; // aa -> a, a } else { dp[1] = 2; // ab -> a, b } // 3文字目 if (S[0] != S[1] && S[1] != S[2]) { dp[2] = 3; // aba -> a, b, a } else { dp[2] = 2; // ?aa -> ?a, a } for (int i = 3; i < n; i++) { if (S[i - 1] == S[i]) { dp[i] = dp[i - 3] + 2; // ??aa -> ?, ?a, a or ?, ?, aa } else { dp[i] = dp[i - 1] + 1; // ?ab -> ?, a, b or ?a, b } } cout << dp[n - 1] << "\n"; return 0; }
ディスカッション
コメント一覧
こんにちは。この問題で躓いていたため、解説大変参考になりました!
本文中の配列の更新式のc_i = c_{i-1} の時の漸化式が
d_2(i) = d_1(i-1)+1
となっていますが、
d_2(i) = d_1(i-2)+1
の打ち間違いかと思います。
また、「一方で、c_{i-1}c_i という文字列に分割するときは、c{i-2}という部分文字列で分割されている『必要』があります。」とありますが、c{i-3}c{i-2} の文字列で分割されている場合ではダメな理由としては「d_1やd_2はそれぞれ二通りの分割の仕方をした場合の分割数の”最大値”であり、c{i-3}c{i-2} のような分割の仕方は、d_2(i) の最大値を与えないから不適」というような認識でよろしいでしょうか?
これに付随して、c_1 = c_2 の場合の d_1(2) の初期値を (そのような分割の仕方は不可能であるにもかかわらず) 1 としているのはどう考えればよろしいでしょうか?
コメントありがとうございます。
指摘があった部分について追記をしました。
部分文字列の必要性の部分ですが、部分文字列は最長で2でありかつ、長さが2の部分文字列が連続して分割されることはないので、そのような分割の仕方がダメである判断できます。
初期値について、配列の定義の遷移が正しくありませんでした。二次元配列で定義すると余計にややこしくしてしまいました。例えば、aaaa という文字列において、d_2{3} = 0 とするしかなくなるなど不都合が多いと思いました。(aa, aa と分割できない)