ARC014 C問題：魂の還る場所 - 忘れても大丈夫

問題. 魂の還る場所

赤青緑の3色からなる $N$ 個のボールが1列に並んでいる． $i \, (1 \le i \le N)$ 番目の色は $s_i$ である．1番目のボールから順番に円筒の左側か右側の好きな方向から入れる．同じ色が2個並ぶとそれらのボールは消える．すべてのボールを入れた後に円筒に入っているボールの数を最小化せよ．

制約： $1 \le N \le 50$

解法．貪欲法

$N$ 個のボールに含まれる赤青緑のボールの個数をそれぞれ $R, B, G$ とすると，答えの下界は $M = (R \bmod 2) + (B \bmod 2) + (G \bmod 2)$ である．

次に，最終的に円筒に入っているボールの個数が $M$ となることを示す．すなわち，下界と上界が一致するので答えは $M$ となる．
消される可能性がある同じ色のボール対は最も近い色同士としても良いことが分かる．例えば，R ... R ... R と並んでいたときに1番目と3番目のRが対となって消すことができるならば，1番目と2番目のRも対として消すことができる．次に，1番目から順番にボールを円筒に詰め込むときに，何番目のボールを詰め込むときでもその時点で円筒に入っているボールの個数は高々3となる．これは，先程の貪欲的に対にすることを意識すると帰納法で示すことができる．

計算時間： $O(N)$

ソースコードを表示

#include <bits/stdc++.h>

using namespace std;

using ll = long long;
using ld = long double;

int main() {
    cin.tie(0); ios::sync_with_stdio(false);
    // cout << setprecision(8) << setiosflags(ios::fixed);

    int n;
    cin >> n;

    string s;
    cin >> s;

    vector<int> cnt(3); // RGB
    for (char c : s) {
        if (c == 'R') ++cnt[0];
        else if (c == 'G') ++cnt[1];
        else ++cnt[2];
    }

    cout << (cnt[0] % 2) + (cnt[1] % 2) + (cnt[2] % 2) << endl;

    return 0;
}