第12回日本情報オリンピック本戦 1-電飾（illumination)

問題

https://img.atcoder.jp/other/joi2013ho/joi2013ho1.pdf

長さNの電飾の各位置の電球は点いているか点いていないかいずれかである。
任意の範囲で電飾の点灯状態を反転させた場合の交互点灯列の最長を求める。
N<10e5

考察

反転範囲を全探索して、などという方法を考えたけれど間に合いそうにありません。
JOIは部分点があるので、この方法でも20点とかは取れそうですが。

だいぶ悩みましたが解法を思いつかず解説AC。

反転範囲を数字に置き換えて連続する３つ分の合計の最大値を求めます。
天才かと思いました。

やり方がわかれば実装は簡単な問題。
ただし初見ではやり方をなかなか思いつけないので難易度５は低すぎかと思いました。

ACしたコード。

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

int main(){
  int n;
  cin>>n;
  int A[100010];
  for(int i=0;i<n;i++){
    cin>>A[i];
  }
  vector<int>vec;
  int temp=A[0];
  int cnt=1;
  for(int i=1;i<n;i++){
    if(A[i] == temp){
      vec.push_back(cnt);
      cnt=1;
      temp=A[i];
    }
    else{
      cnt++;
      temp=A[i];
    }
  }
  vec.push_back(cnt);
  
  if(vec.size()<=3){
    cout<<n<<endl;
    return 0;
  }
  
  int maxans=0;
  for(int i=0;i<vec.size()-2;i++){
    maxans=max(maxans,vec.at(i)+vec.at(i+1)+vec.at(i+2));
  }
  cout<<maxans<<endl;
    
  return 0;
}