0527 Seting Go Stones (碁石ならべ)

http://rose.u-aizu.ac.jp/onlinejudge/ProblemSet/description.jsp?id=0527
規則に従って白黒の碁石を並べていったときに，最終的に白が何個あるかとう問題．

言われた通りにシミュレーションすると最悪 O(n^2) になって n <= 10000 だと TLE しそう．
連続する同じ色の碁石の数のリストを持って碁石を置く度にこれを更新することで O(n) で解ける．

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main()
{
  int N;
  while (cin >> N && N != 0) {
    int x;
    cin >> x;
    vector<int> v(1, 1);
    int ans = x == 0 ? 1 : 0;
    int prev = x;
    for (int i = 1; i < N; i++) {
      cin >> x;
      if (prev == x) {
        v.back()++;
        if (x == 0) {
          ans++;
        }
      } else {
        if (i % 2 == 0) {
          v.push_back(1);
          if (x == 0) {
            ans++;
          }
        } else {
          if (v.size() == 1) {
            v.back()++;
            if (x == 0) {
              ans = v.back();
            } else {
              ans = 0;
            }
          } else {
            const int y = v.back();
            v.pop_back();
            v.back() += y + 1;
            if (x == 0) {
              ans += y + 1;
            } else {
              ans -= y;
            }
          }
        }
      }
      prev = x;
    }
    cout << ans << endl;
  }
  return 0;
}