AtCoder AGC 026 A - Colorful Slimes 2 (灰色, 200 点)

最初スライムの色の種類が 種類かと思ってしまって、 の場合が面倒じゃないかと思ってしまった。

Colorful Slimes 2 へのリンク

問題概要 (AGC 026 A)

1〜10000 の整数からなる 要素の数列が与えられる。

• 数列の好きな箇所を選んで 1〜10000 のうちの好きな数字に置き換える

という操作を最小回数実施して、「数列のどの隣り合う二項も相異なる」という状態にせよ。

制約

• 

解法

Greedy に変えていけばよいが、「1 1 1」とかだったら「2 1 2」ではなく「1 2 1」とかにしたい。

左から見て行って、隣り合う箇所を見つけたら右側を変更していけばよい。ただし、その変更した値が、さらに右側の数字とも同じにならないようにしたい。-1 とかに変更しておけばよさそう。本当は -1 には変更できないが 10000 色もあるので「仮の変更色」として -1 で構わない。

ようにすればよさそう。

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

int N;
vector<int> a;

int main() {
  cin >> N;
  a.resize(N); for (int i = 0; i < N; ++i) cin >> a[i];
  
  int res = 0;
  for (int i = 1; i < N; ++i) {
    if (a[i] == a[i-1]) {
      a[i] = -1;
      ++res;
    }
  }
  cout << res << endl;
}