ARC024B 赤と黒の木

問題

B - 赤と黒の木

円周上に赤と黒の木が並んでいて、両隣が同じ色の木は翌日に色が変わります。
色が変わらなくなるまでの日数を出力します。
変わり続ける場合は-1を出力します。

考察

まずすべての木が同じ色の場合はすべての木が永久に赤黒を繰り返します。

そうでない場合について、少ない数のモデルで確かめてみると連続している木の数が１日毎に２づつ減っていくようです。

赤と黒のそれぞれの木の最長の連続数を求めて１を加えて２で割る（あるいは２で割って１を加える）ことで答えが求まりそうです。

円周なので数え初めと数え終わりが同じ色の場合に両者を足す工夫を考えました。
具体的には、最初と終わりが同じ色の場合にもう１周回すようにしました。
冗長なようにも見えますがコピペなので手間はかかりません。

コード

無事にACしました。
自力で解けて嬉しいです。

#include <bits/stdc++.h>
using namespace std;

int main(){
  int N;
  cin>>N;
  int C[N];
  int flag1=0;
  int flag2=0;
  for(int i=0;i<N;i++){
    cin>>C[i];
    if(C[i]==0){
      flag1=1;
    }
    if(C[i]==1){
      flag2=1;
    }    
  }
  if(flag1*flag2==0){
    cout<<-1<<endl;
    return 0;
  }

  int cnt=0;
  int maxwcnt=0;
  int maxbcnt=0;
  
  //w最長探索
  for(int i=0;i<N;i++){
    if(C[i]==0){
      cnt++;
      maxwcnt=max(maxwcnt,cnt);
    }
    else{
      cnt=0;
    }
  }
  if(C[0]==0 && C[N-1]==0){
    for(int i=0;i<N;i++){
      if(C[i]==0){
        cnt++;
        maxwcnt=max(maxwcnt,cnt);
      }
      else{
        cnt=0;
      }
    }
  }
  
  //b最長探索
  cnt=0;
  for(int i=0;i<N;i++){
    if(C[i]==1){
      cnt++;
      maxbcnt=max(maxbcnt,cnt);
    }
    else{
      cnt=0;
    }
  }
  if(C[0]==1 && C[N-1]==1){
    for(int i=0;i<N;i++){
      if(C[i]==1){
        cnt++;
        maxbcnt=max(maxbcnt,cnt);
      }
      else{
        cnt=0;
      }
    }
  }  
  
  cout<<(max(maxbcnt,maxwcnt)+1)/2<<endl;
  return 0;
}