SRM504 Div1 Easy - MathContest
問題
黒と白の玉が入ったスタックを上から順に処理していく
白の玉を取り出したらスタックの上下がひっくり返る
黒の玉を取り出したら中の玉の色が全て反転する
全ての玉を取り出すまでに黒の玉を何度取り出すことになるか計算
解法
実装をする
実装
反転をreverseでやると遅いから見終わった位置を上下(l,r)それぞれで持っといて白を引いたらswap(l,r)
(いまどっちの方向からスタックを見てるかを変数で持ってもいいけど分岐がめんどくさそうだから)
色の反転もいま反転してるかを変数vで持っておく
↓の実装だとwhileループを終えた後l(=r)の玉をまだ取り出してないから最後そこだけ注意
class MathContest { public: int countBlack(string t, int p) { string s; rep(i,p) s += t; int res = 0, l = 0, r = s.size()-1, v = 0; while (l!=r) { if ((s[l]=='W' && !v) || (s[l]=='B' && v)) { l += (l<r ? 1 : -1); swap(l,r); } else { res++; l += (l<r ? 1 : -1); v ^= 1; } } return res + ((s[l]=='B' && !v) || (s[l]=='W' && v)); } };