意外とすぐにわからなかったんやけど...
問題概要
英小文字からなる文字列 が与えられる。以下の条件をみたす最大の正整数 を求めよ。
- を空でない 個の文字列へと分割したとき、連続する文字列は相異なる
制約
Greedy は嘘
パッと思い浮かぶ Greedy 解法として、次のものがあるかもしれない。
- 1 文字で区切れるなら区切って、区切れないなら 2 文字で区切る
しかし "aaaaa" をやろうとすると詰まってしまう。Greedy にやると、
a | aa | ...
と区切ることになるけれど、ラスト 2 文字は上手く分割できないのだ。他の解法を考える必要がある。
解法 (1):DP で殴る
区間分割と言われるといかにも DP でできそう。重要な考察要素としては
「長さ 3 以上の区間は不要」
ということ。仮に長さ 3 以上の文字列の区間があったとき、区間分割数を減らすことなく長さ 3 以上の区間を解消することができるからだ (実際にちゃんと示すのは結構場合分けが大変)。
というわけで
- dp[ i ][ 1 or 2 ] := 最初の i 文字分をいくつかの区間に分割することを考えたときに、最後の区間の文字列の長さが 1 または 2 になるようにしたときの、区間の個数の最大値
という DP で解ける。計算量は 。
#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 は嘘だと言ったが、それをちょっと改良すれば嘘ではなくなる!!!
アルメリアさんの記事を参照!!