Dividing a String [AtCoder Grand Contest 037 A]

https://atcoder.jp/contests/agc037/tasks/agc037_a

前提知識

• DP

解説

https://atcoder.jp/contests/agc037/submissions/6964393

AGCの頭ということで貪欲で解きたい気持ちをこらえて解法を考える。
順位賞を見ると爆速で解いている人もいるが、結構落ちている人もいる。
こういう場合は、貪欲で落ちている人が多そうなので、ちゃんと考える。

今回は性質を見抜くのが本質であるが、ひらめきとしか言いようがない。
分割していくが、1文字か2文字で分割するのが最善手である。
よって、dp[i][pre] := i文字目まで使っていて、以前にpre文字分使用している。
これで1つ前の文字列が特定できるので、それと被るのを避けて遷移させればいい。

string S;
int N;
int dp[201010][3];
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> S;
    N = S.length();
    S += "####";

    rep(i, 0, N + 1) rep(pre, 0, 3) dp[i][pre] = -inf;
    dp[0][0] = 0;

    rep(i, 0, N) rep(pre, 0, 3) rep(d, 1, 3) if (0 <= dp[i][pre]) {
        if (pre == d) {
            if (d == 1) {
                if (S[i - 1] == S[i]) continue;
            }
            else {
                if (S[i - 2] == S[i] and S[i - 1] == S[i + 1]) continue;
            }
        }
        chmax(dp[i + d][d], dp[i][pre] + 1);
    }

    cout << max(dp[N][1], dp[N][2]) << endl;
}