Colorful Slimes 2 [AtCoder Grand Contest 026 A]

https://beta.atcoder.jp/contests/agc026/tasks/agc026_a

考察過程

1. 項目数が100で色が10^4なので、色を変更した場合は他の項目と違う色を選ぶのが最適
2. 貪欲に最適な動きをすれば良さそう
3. 貪欲にやるには連続する3つの項目が同じ色の場合に真ん中の項目の色を変更すると3項目一気に解消できてお得
4. あとは、連続する2つの項目が同じ色なものを解消する

解法

https://beta.atcoder.jp/contests/agc026/submissions/2850689

貪欲法。
1. 連続する3つの項目が同じ色の場合に真ん中の項目の色を変更
2. 連続する2つの項目が同じ色の場合にどちらかの項目の色を変更
これを順番に貪欲にやって色の変更回数を数えれば答え。

int N, A[101];
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N;
    rep(i, 0, N) cin >> A[i];
    
    int ans = 0;
    rep(i, 1, N - 1) if (A[i - 1] == A[i] and A[i] == A[i + 1]) {
        ans++;
        A[i] = -1;
    }
 
    rep(i, 1, N) if (A[i - 1] == A[i]) ans++;
    cout << ans << endl;
}