AtCoder ABC 124 C - Coloring Colorfully (灰色, 300 点)

一見複雑だけど、実質 2 通りしかないというやつ

問題へのリンク

問題概要

長さが の 0-1 列が与えられる。何個かについて 0 と 1 を入れ替えることで、

• 0 と 1 が交互に並んでいる状態

にしたい。そのようなことが可能な方法のうち、入れ替える数字の個数の最小値を求めよ。

制約

• 

考えたこと

ちょっと複雑な設定で一瞬、「ん？」となりそうになってしまうが、よく考えると最終的に出来上がるものが

• 01010101010101...
• 10101010101010...

という風に実質 2 通りしかない。よって、それぞれについて、そうするのに必要な回数を求めて小さい方を答えれば OK。

#include <iostream>
#include <string>
using namespace std;

int main() {
    string S; cin >> S;

    // スタートが 0 か 1 か
    int res = 1<<29;
    for (int start = 0; start <= 1; ++start) {
        int val = start; // それぞれの数値でスタート
        int count = 0;
        for (int i = 0; i < S.size(); ++i) {
            // 目指すものと異なる部分をカウント
            if (S[i] - '0' != val) ++count;

            // 入れ替え
            val = 1 -val;
        }
        res = min(res, count);
    }
    cout << res << endl;
}