0527 Setting Go Stones

http://rose.u-aizu.ac.jp/onlinejudge/ProblemSet/description.jsp?id=0527

方針

同じ色の碁石が連続する部分を、部分の始まり、部分の終わり、色を要素にもつ構造体で表した。

ソース

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

#define REP(i,a,b) for(i=a; i<b; ++i)
#define rep(i,n) REP(i,0,n)

struct range{
  int start,end,color;
  range() {;}
  range(int start,int end,int color) : start(start), end(end), color(color) {;}
};

int main() {
  int n,i,j,k;
  ios_base::sync_with_stdio(false);
  while(cin>>n, n) {
    vector<range> stones;
    rep(i,n) {
      cin>>j;
      if(stones.empty()) stones.push_back(range(i+1,i+1,j));
      else if(i%2==0) {
	if(j == stones.back().color) stones.back().end++;
	else stones.push_back(range(i+1,i+1,j));
      }else{
	if(stones.back().color == j) stones.back().end++;
	else {
	  int st = i+1;
	  while(!stones.empty()) {
	    if(stones.back().color == j) {
	      stones.push_back(range(st,i+1,j));
	      break;
	    }else{
	      st = stones.back().start;
	      stones.pop_back();
	    }
	  }
	  if(stones.empty()) stones.push_back(range(1,i+1,j));
	}
      }
    }

    int ans = 0;
    rep(i,stones.size())
      if(stones[i].color == 0) ans += stones[i].end - stones[i].start + 1;

    cout<<ans<<endl;
  }
}