けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

AtCoder AGC 037 A - Dividing a String (灰色, 300 点)

意外とすぐにわからなかったんやけど...

問題概要

英小文字からなる文字列  S が与えられる。以下の条件をみたす最大の正整数  K を求めよ。

  •  S を空でない  K 個の文字列へと分割したとき、連続する文字列は相異なる

制約

  •  1 \le |S| \le 2 \times 10^{5}

Greedy は嘘

パッと思い浮かぶ Greedy 解法として、次のものがあるかもしれない。

  • 1 文字で区切れるなら区切って、区切れないなら 2 文字で区切る

しかし "aaaaa" をやろうとすると詰まってしまう。Greedy にやると、

a | aa | ...

と区切ることになるけれど、ラスト 2 文字は上手く分割できないのだ。他の解法を考える必要がある。

解法 (1):DP で殴る

区間分割と言われるといかにも DP でできそう。重要な考察要素としては

「長さ 3 以上の区間は不要」

ということ。仮に長さ 3 以上の文字列の区間があったとき、区間分割数を減らすことなく長さ 3 以上の区間を解消することができるからだ (実際にちゃんと示すのは結構場合分けが大変)。

というわけで

  • dp[ i ][ 1 or 2 ] := 最初の i 文字分をいくつかの区間に分割することを考えたときに、最後の区間の文字列の長さが 1 または 2 になるようにしたときの、区間の個数の最大値

という DP で解ける。計算量は  O(N)

#include <bits/stdc++.h>
using namespace std;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }

int main() {
    string S;
    cin >> S;
    int N = S.size();
    vector<vector<int>> dp(N+1, vector<int>(3, -1));
    dp[0][0] = 0;
    for (int i = 0; i < N; ++i) {
        for (int j = 0; j <= min(i, 2); ++j) {
            string suffix = S.substr(i - j, j);
            for (int add = 1; add <= 2 && i + add <= N; ++add) {
                // 同じものが連続しないなら更新
                if (S.substr(i, add) != suffix) {
                    chmax(dp[i + add][add], dp[i][j] + 1);
                }
            }
        }
    }
    cout << max(dp[N][1], dp[N][2]) << endl;
}

解法 (2):Greedy を改良

最初に Greedy は嘘だと言ったが、それをちょっと改良すれば嘘ではなくなる!!!

アルメリアさんの記事を参照!!

betrue12.hateblo.jp