AtCoder Regular Contest 024 B - 赤と黒の木

手を動かすと答えが分かる問題だった。

問題

円形にN本の木が並んでる。
木はそれぞれ赤または黒の二色である。
それぞれの木は自分の色と両隣の色が同じなら次の日に自分の色が変わる。
何日目に全ての木の色が変わらなくなる日を出力せよ
また木が変化し続けるならば-1を出力せよ

解法

同じ色がいくつ連続しているかを考える
3○○○→○●○ 2日
5○○○○○→○●●●○→○●○●○ 3日
7○○○○○○○→○●●●●●○→○●○○○●○→○●○●○●○ 4日

連続数をxと考えてあげると一日ごとに
2ずつ減り連続数xが3未満になったら変化しない
よって求める答えは円形の最長の色の連続数をmax_cntとすると
(max_cnt + 1)/2が答えとなる。
円形の最長の連続数を求めるならば
例えば、001010ならば
001010 + 001010 = 001010001010として数列を倍にして考えればよい

• 1の判定は全て同じ色なら変化し続ける。

コード

#include <map>
#include <set>
#include <list>
#include <cmath>
#include <queue>
#include <stack>
#include <cstdio>
#include <string>
#include <vector>
#include <complex>
#include <cstdlib>
#include <cstring>
#include <numeric>
#include <sstream>
#include <iostream>
#include <algorithm>
#include <functional>

#define mp       make_pair
#define pb       push_back
#define all(x)   (x).begin(),(x).end()
#define rep(i,n) for(int i=0;i<(n);i++)

using namespace std;

typedef    long long          ll;
typedef    unsigned long long ull;
typedef    vector<bool>       vb;
typedef    vector<int>        vi;
typedef    vector<vb>         vvb;
typedef    vector<vi>         vvi;
typedef    pair<int,int>      pii;

const int INF=1<<29;
const double EPS=1e-9;

const int dx[]={1,0,-1,0},dy[]={0,-1,0,1};
int n;
int main(){
	cin>>n;
	string tmp ="";
	for(int i = 0;i < n;i++){
		char c;
		cin>>c;
		tmp +=c;
	}
	tmp +=tmp;
	// cout <<"tmp = "<<tmp<<endl;
	char pre =tmp[0];
	int cnt = 1;
	int max_cnt = 1;
	for(int i = 1;i < tmp.length();i++){
		if(pre == tmp[i]){
			cnt++;
			max_cnt = max(max_cnt,cnt);
		}else{
			max_cnt =max(max_cnt,cnt);
			cnt = 1;
		}
		pre = tmp[i];
	}
	if(cnt == 2*n){
		cout <<-1<<endl;
		return 0;
	}
	// cout <<"max_cnt = "<<max_cnt<<endl;
	cout <<(max_cnt + 1)/2<<endl;
	return 0;
}