AtCoder Regular Contest #024
問題文
円周上に $N$ 個の木が並んでいて,木の色は赤か黒かのどちらかである.
$1$ 日目の木の色が全て与えられる.
日が変わる瞬間に,自分と両隣の木の $3$ つの木が全て同じ色であった場合は,自分の木の色を変えるという性質がある.
(色が変わる場合は,全ての木が同時に色が変わる)
何日目以降に木の色が全く変化しなくなるかを求める問題.
永遠と木の色が変わり続けるならそれを指摘する.
全ての木の色が同じであれば,全ての木が色を変え続けるので,永遠と変わり続ける.
そうでなければ,同じ色が連続している部分の長さが $L$ であれば,その部分は日が変わると両端の木を除いて色が変わり,同じ色の部分の長さは $L-2$ に変わっていく.
よって,その部分の色が変わらなくなるのは $\lfloor (L+1)/2 \rfloor$
なので,$\lfloor (L+1)/2 \rfloor$ の最大値が答え.
#include<bits/stdc++.h>
using namespace std;
#define REP(i,a,b) for(i=a;i<b;i++)
#define rep(i,n) REP(i,0,n)
#define mygc(c) (c)=getchar_unlocked()
#define mypc(c) putchar_unlocked(c)
void reader(int *x){int k,m=0;*x=0;for(;;){mygc(k);if(k=='-'){m=1;break;}if('0'<=k&&k<='9'){*x=k-'0';break;}}for(;;){mygc(k);if(k<'0'||k>'9')break;*x=(*x)*10+k-'0';}if(m)(*x)=-(*x);}
void writer(int x, char c){int i,sz=0,m=0;char buf[10];if(x<0)m=1,x=-x;while(x)buf[sz++]=x%10,x/=10;if(!sz)buf[sz++]=0;if(m)mypc('-');while(sz--)mypc(buf[sz]+'0');mypc(c);}
int N, c[1000000];
int main(){
int i, j, k;
int res = 0, tmp;
reader(&N);
rep(i,N) reader(c+i);
REP(i,1,N) if(c[i] != c[0]) break;
REP(i,N,2*N+1) c[i] = c[i-N];
tmp = 1;
REP(i,1,2*N+1){
if(c[i] != c[i-1]) tmp = 1;
else tmp++;
res = max(res, tmp);
}
if(res > N+1) res = -1;
else res = (res + 1) / 2;
writer(res, '\n');
return 0;
}
Current time: 2024年04月20日14時29分22秒
Last modified: 2014年08月06日01時40分28秒 (by laycrs)
Tags: Competitive_Programming AtCoder AtCoder_Regular_Contest ARC024 ARC_B
トップページに戻る
Logged in as: unknown user (not login)