AOJ 0527 Setting Go Stones
http://rose.u-aizu.ac.jp/onlinejudge/ProblemSet/description.jsp?id=0527
うまいことやって碁石を数える時間を短縮する。
同じ色の碁石を個数でまとめてスタックに突っ込みました。
スタックが空かそうでないかとかを見ないといけないので場合分けがちょっと多くなりました。
main(){ int n; while(cin>>n,n){ stack<PI> go; rep(i,n){ int st; cin>>st; if(i%2){ PI tp=go.top();go.pop(); if(tp.F!=st){ tp.S++; go.push(tp); }else{ if(!go.empty()){ PI tp2=go.top();go.pop(); tp2.S+=tp.S+1; go.push(tp2); }else{ tp.S++; tp.F=!tp.F; go.push(tp); } } }else{ if(!go.empty()){ PI tp=go.top();go.pop(); if(tp.F==!st){ tp.S++; go.push(tp); }else{ go.push(tp); go.push(mp(!st,1)); } }else go.push(mp(!st,1)); } } int ans=0; while(!go.empty()){ int col=go.top().F,num=go.top().S; go.pop(); if(col)ans+=num; } cout<<ans<<endl; } }