AtCoder Regular Contest #024 B問題 - 赤と黒の木

Source

AtCoder Regular Contest #024
問題文

問題概要

円周上に $N$ 個の木が並んでいて，木の色は赤か黒かのどちらかである．
$1$ 日目の木の色が全て与えられる．
日が変わる瞬間に，自分と両隣の木の $3$ つの木が全て同じ色であった場合は，自分の木の色を変えるという性質がある．
（色が変わる場合は，全ての木が同時に色が変わる）
何日目以降に木の色が全く変化しなくなるかを求める問題．
永遠と木の色が変わり続けるならそれを指摘する．

解法

全ての木の色が同じであれば，全ての木が色を変え続けるので，永遠と変わり続ける．
そうでなければ，同じ色が連続している部分の長さが $L$ であれば，その部分は日が変わると両端の木を除いて色が変わり，同じ色の部分の長さは $L-2$ に変わっていく．
よって，その部分の色が変わらなくなるのは $\lfloor (L+1)/2 \rfloor$ なので，$\lfloor (L+1)/2 \rfloor$ の最大値が答え．

C++によるスパゲッティなソースコード

#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月19日22時30分21秒
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)

ログイン：