第７回日本情報オリンピック 本選 「碁石ならべ」

こういう系の問題一番苦手。
実装力がない。
オーダーから察するにO(N)問題。

int s[i];
（i番目について、白の碁石の連続している数）
int k[i];
(i番目について、黒の碁石の連続している数)
で値をもっておきあとはいわれたとおりにやる。

#include <cstdio>
#include <iostream>

using namespace std;
int n,s[100002]={0},k[100002]={0};
bool d[100002];
int ans = 0;
int main(){
 while(1){
   ans = 0;
  scanf("%d",&n);
  if(n == 0)break;
  int tmp;
  for(int i = 1;i <= n;i++){
    scanf("%d",&tmp);
    if(tmp) d[i] = true;
    else d[i] = false;
  }
  bool pre = true;
  for(int i = 1;i <= n;i++){
    if(i % 2 == 1 || pre == d[i]){
      if(d[i]){
	k[i] = k[i-1] + 1;
	s[i] = 0;
      }else{
	s[i] = s[i-1] + 1;
	k[i] = 0;
	ans++;
      }
    }else{
      if(d[i]){
	ans -= s[i-1];
	k[i] = s[i-1] + 1 + k[i-s[i-1]-1];
	s[i-1] = 0;
      }else{
	ans += k[i-1] + 1;
	s[i] = k[i-1] + 1 + s[i-k[i-1]-1];
	k[i-1] = 0;    
      }
    }
    pre = d[i];
  }
  
  printf("%d\n",ans);
 }
  return 0;
  
}