AGC016: A - Shrinking

入力が小さいときは難しく考えず素直に全探索しましょうという問題．競プロの基本は全探索．

問題

• AGC016: A - Shrinking

解説

• editorial

www.youtube.com

解説をそのまま引用．素直に解説の通りに実装すれば良い．

英小文字 c をひとつ固定します．最終的に s が単一の文字 c のみからなるようにしたいとします．すると，各操作では c を優先的に選べばよいです．よって，シミュレーションによって必要な操作回数が求まります．以上より，c を a から z まで全探索し，操作回数の最小値を求めればよいです．

アルファベットは 26 文字（実際は入力を 1 文字ずつ std::set に入れた文字集合），入力は最大 100 文字なので計算量的に全探索でシミュレーションを行う．

#include <iostream>
#include <string>
#include <set>
using namespace std;
using ll = long long;

int main() {
    // input
    string S;
    cin >> S;
    set<char> chars;
    for (ll i = 0; i < S.length(); ++i) chars.insert(S[i]);  // チェックするための文字集合

    if (chars.size() == 1) {
        // 全部同じ文字
        cout << 0 << "\n";
        return 0;
    }

    // calculation
    ll res = 100, times;
    for (auto key = chars.begin(); key != chars.end(); ++key) {
        // prepare simulation
        string str = S;
        bool flag = true;  // 全ての文字が同じでない:true
        times = 1;  // 必ず一回は縮める（全部が等しいというのはあらかじめ除いてある）

        while (flag) {
            string vacant;
            flag = false;
            for (ll i = 0; i < str.length()-1; ++i) {
                // shrink
                if (str[i] == *key || str[i+1] == *key) {
                    vacant += *key;
                } else {
                    vacant += str[i];
                    flag = true;  // 異なる文字が混じってしまったらループは続く
                }
            }

            if (flag) {
                // 1回の操作後，違う文字が混じっていた場合
                str = vacant;
                times++;
            }
        }

        // update
        res = min(res, times);
    }

    cout << res << "\n";

    return 0;
}

反省

入力の制約が小さいときはまずは全探索を視野に入れて考察することを心掛ける．

参考

atcoder.jp