[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-1) + 1
\end{eqnarray}\]

\( 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} \) という部分文字列で分割されている必要があります。

コード