はまやんはまやんはまやん

hamayanhamayan's blog

Wide Flip [AtCoder Regular Contest 088 D]

https://beta.atcoder.jp/contests/arc088/tasks/arc088_b

解法

https://beta.atcoder.jp/contests/arc088/submissions/1897988

貪欲法で解く。
最初に、0のグループと1のグループで個数をカウントして配列vを作る。
目標としては全て0にするか、全て1にすることを考える(全て1になったら全ての区間で0に反転させればいい)。
前からか後ろから処理していくので、配列vをデキューdに移し替えておこう。

デキューの中身が{d[0], d[1], ... , d[n - 2], d[n-1]}とする。
この場合に行える最適戦略は「d[0]~d[n-2]を全てスワップする」か「d[1]~d[n-1]を全てスワップする」ことである。
これは範囲がより大きい方でやればいい。
どちらの範囲が広いかはa=d[0]とb=d[n-1]を比較する。
a<bならば、d[1]~d[n-1]をスワップすることにする。d[0]以外スワップするとd[0]とd[1]は同色になるので併合する。
そうでない場合も同様にやる。
これを2個になるまで繰り返す。
2個になったら、大きい方をスワップして1つにする。
 
答えはこのように行動していった過程での最小スワップ区間である。
なお、上の貪欲法は未証明なので、本当にちゃんと動いているかは分からない。

string S;
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> S;
 
    int N = S.length();
    vector<int> v;
    char p1 = S[0]; int p2 = 0;
    rep(i, 1, N) if (S[i] != p1) v.push_back(i - p2), p2 = i, p1 = S[i];
    v.push_back(N - p2);
 
    deque<int> d;
    fore(i, v) d.push_back(i);
 
    int ans = N;
    while (1 < d.size()) {
        int a = d.front();
        int b = d.back();
 
        if (d.size() == 2) {
            ans = min(ans, max(a, b));
            break;
        }
 
        if (a < b) {
            int x1 = d.front(); d.pop_front();
            int x2 = d.front(); d.pop_front();
 
            ans = min(ans, N - a);
            d.push_front(x1 + x2);
        } else {
            int x1 = d.back(); d.pop_back();
            int x2 = d.back(); d.pop_back();
 
            ans = min(ans, N - b);
            d.push_back(x1 + x2);
        }
    }
 
    printf("%d\n", ans);
}