AtCoder ABC 047 C - 一次元リバーシ (4Q, 茶色, 300 点)

綺麗な言葉で条件を言い換えよう！

• 問題へのリンク

問題概要

一列に白色碁石と黒色碁石が合計 個並んでいる。

左右のいずれかに白色碁石と黒色碁石を置いていく。このとき、オセロのルールに基づいて石の色がひっくり返る。

すべての色を同色にするのに必要な操作回数の最小値を求めよ。

制約

• 

考えたこと

この手の問題では、まずはいろいろなケースを実験してみるとよいだろう。たとえば、

• "BBWWW"：右から B を打つことで、すべて B になるので 1 回
• "BBWWWBBB"：右か W を打ち、その後 B を打つことで、すべて B になるので 2 回（1 回ではできない）
• "BBWWWBBBW"：右から B、W、B の順に打つことで、すべて B になるので 3 回（2 回ではできない）

という感じになる。ここから見えてくることは、もとの盤面で、B と W の変わり目が多ければ多いほど、必要回数が増えるのではないか？？ということだ。もっとちゃんと整理すると、

---

もとの盤面で、B と W の変わり目が 箇所あるとき、最小回数 回であろう

---

と予想できる。コンテスト本番ならば、この段階でもう提出しても良いと思う。ここでは念のために、簡単に証明してみよう。

最小回数が 回であることの証明

具体的には、次の 2 つを示せば良いです。

• すべて同色にするためには、少なくとも 回以上必要であること
• どんな盤面でもかならず 回で同色にできること

前者は、「1 回の操作によって、W と B の変わり目の個数が 2 個以上減少することはない」ことによって示せます。

後者は、たとえば、右側から「右端の碁石と異なる色の石を置いていく」を繰り返すことで実現できます。

コード

#include <bits/stdc++.h>
using namespace std;

int main() {
    string S;
    cin >> S;
    int res = 0;
    for (int i = 0; i+1 < S.size(); i++) {
        if (S[i] != S[i+1]) res++;
    }
    cout << res << endl;
}