AtCoder AGC 016 A - Shrinking (緑色, 300 点)

一瞬コーナーケースがないかと怖くなる

問題へのリンク

問題概要

長さ の文字列 が与えられる。この文字列に対し、以下の操作を好きな回数だけ行うことができる。文字列を「単一の文字からなる状態」にするのに必要な操作回数の最小値を求めよ。

• 文字列の各「隣接 2 文字」に対して、その 2 文字のうちのどちらかを選ぶ
• それらを concatenate する (出来上がる文字列は元の文字列より 1 文字少ない)

制約

• 

考えたこと

かけても大丈夫なのでゆったりと考える。各文字について、その文字一色にするのに必要な操作回数を考えよう。たとえば、a に揃えるとき、

xxxaaaxxxxaxxxxxaa

といった文字列だった場合、

• 最初の xxx は、3 回で消せる
• 次の xxxx は、左右から合計 4 回で消せる
• 次の xxxxx は、左右から合計 5 回で消せる

という感じになっている。ランレングス圧縮して、a 以外からなる区間についての長さの最大値を取れば OK。

#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; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }

int main() {
    string S;
    cin >> S;
    int res = (int)S.size(); // INF
    for (char c : S) {
        int tmp = 0;
        for (int i = 0; i < S.size();) {
            int j = i;
            while (j < S.size() && !((S[j] == c) ^ (S[i] == c))) ++j;
            if (S[i] != c) chmax(tmp, j-i);
            i = j;
        }
        chmin(res, tmp);
    }
    cout << res << endl;
}