ARC 024 B

今回はこの問題です。

arc024.contest.atcoder.jp

赤または黒色の木が円周上にn本生えています。この木は１日ごとに、隣の2本の木と自分の色が同じであるとき、異なる色に変化します。隣の木が次にどうなるかは関係なく、その日の状態のみをみて変化します。何日目に木の色が変化しなくなるかを求めなさい、という問題です。

回答はこちら。

    #include <cstdio>
    #include <iostream>
    #include <cmath>
    #include <cstring> 
    #include <sstream>
    #include <algorithm>
    #include <cstdlib>
    #include <map>
    #include <queue>
    #include <utility>
    #include <vector>
    #include <set>
    #include <memory.h>
    #include <iomanip>
    #include <bitset>
    #include <list>
    #include <stack>
     
    using namespace std;
     
    #define mod 1000000007
     
    int main()
    {
        int n;
        cin >> n;
        int c[100001];
        for(int i = 0; i < n; i++){
            cin >> c[i];
        }
        vector<int> renzokunum;
        int nowcolor = c[0];
        int cnt = 1;
        for(int i = 1; i < n; i++){
            if(c[i] == nowcolor){
                cnt++;
            } else {
                renzokunum.push_back(cnt);
                cnt = 1;
                nowcolor = c[i];
            }
        }
        if(c[n - 1] == c[0]){
            if(renzokunum.size() == 0) renzokunum.push_back(cnt);
            else renzokunum[0] += cnt;
        } else {
            renzokunum.push_back(cnt);
        }
        if(renzokunum.size() == 1){
            cout << -1 << endl;
            return 0;
        }
        int maxrenzoku = 0;
        for(int i = 0; i < renzokunum.size(); i++){
            // cout << renzokunum[i] << endl;
            maxrenzoku = max(maxrenzoku, renzokunum[i]);
        }
        cout << maxrenzoku / 2 + maxrenzoku % 2 << endl;
        return 0;
    }

まず同じ色の木がいくつ連続して並んでいるかを数えます。このとき、n - 1番目の木と0番目の木が隣り合って並んでいることに注意します。そのうち最大値を求めます。この木の列が色の変化がなくなるまでかかる日数が答えになります。日数は最大値 / 2 + 最大値 % 2で求められます。