[AtCoder] AGC 037 A – Dividing a String

2019年10月5日

問題

方針

下記の方針は間違いを含んでいるので追記を見てください。

文字列 \( 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;
}