最初に置く石の条件とか適当に付け加えてしまったせいで汚いソースになったけど方針としては、
同じ色で連続しているのを1つの要素にまとめる。
奇数番目だったら普通に置く。
(といっても、今の右端の色と同じだったらその要素に足すだけで、違ったら新しく要素追加して1にするんだけど)
違う色置こうとして、かつ偶数番目だったら、
右端の要素の個数+右端から1コ前の要素の個数 + 1(これから置くやつ)
を右端の要素として再編。
元の右端の要素はpop_back()されて、右端の1つ前だった要素(新しい右端)にその値が足されるイメージ。
黒を+,白を-の値にして扱った。
#include <iostream> #include <vector> using namespace std; #define rep(i,n) for(int i=0;i<n;i++) int main(){ int n; while(cin >> n , n){ int dp[100000] = {0}; int pos = 0; rep(i,n){ int c; cin >> c; if((i+1)%2 == 1){ //odd if(dp[pos] == 0){ if(c)dp[pos]++; else dp[pos]--; continue; } if(c == 1 && dp[pos] > 0){ dp[pos]++; }else if(c == 0 && dp[pos] < 0){ dp[pos]--; }else{ pos++; if(c == 1)dp[pos]++; else dp[pos]--; } }else{ if(c == 1 && dp[pos] > 0){ dp[pos]++; }else if(c == 0 && dp[pos] < 0){ dp[pos]--; }else{ if(pos == 0){ dp[pos] *= -1; }else{ dp[pos-1] -= dp[pos]; dp[pos] = 0; pos--; } if(c == 1) dp[pos]++; else dp[pos]--; } } } int sum = 0; rep(i,100000){ if(dp[i] < 0)sum += dp[i]; } cout << -sum << endl; } }