Problem 0527 : Seting Go Stones

碁石ならべ
http://rose.u-aizu.ac.jp/onlinejudge/ProblemSet/description.jsp?id=0527

• 問題概要

碁石をならべる。
一直線に。
奇数回目に並べたときに、その置いた石と色が違う石が連続していたら、
オセロみたくひっくり返る。
最後に白い石はなんこ？
入力は石の数と置いていく色。

• 解法

書くだけ、なんだけど、
ただ書いちゃうと、100000*100000 = 10000000000 弱？になるので、
同じ色のれんぞくを一まとまりとしてみると簡単。
つまり、色と数の情報をもったクラスなり構造体なりつくってやってそれを、スタックに詰めました。

• ソース

#include<iostream>
#include<stack>
#include<algorithm>

using namespace std;

class Stone{
public:
  int c, num;
};

main(){

  int n;

  while(cin >> n){
    if(n == 0)break;
    stack<Stone> S;
    for(int i=0; i<n; i++){
      Stone s;
      cin >> s.c;
      s.num = 1;
      if(i == 0){
	S.push(s);
	continue;
      }
      Stone top = S.top();
      S.pop();
      if(top.c == s.c){
	top.num++;
	S.push(top);
	continue;
      }

      if( (i+1)%2 == 1){
	S.push(top);
	S.push(s);
	continue;
      }
      
      s.num += top.num;
      if(S.empty()){
	S.push(s);
	continue;
      }
      S.top().num += s.num;
    }
    int ans = 0;
    while(!S.empty()){
      Stone s = S.top();S.pop();
      if(s.c == 0)ans += s.num;
    }
    cout << ans << endl;
  }
}