SRM 504 easy MathContest

問題概要

スタックに黒と白のボールが詰まってる。

• 白を取り出すとスタックに入ってる順番がリバースされる。
• 黒を取り出すとスタックの中のボールの色が変わる

スタックの中身を全部取り出すとき、最終的に何個黒をとりだすことになりますか？

解法

• ん、シミュレーションしていいのかな。
• ボール100000を超えないなら大丈夫だろう、でもほんとに大丈夫かな。
• 想定誤答は黒と白を実際にいちいち塗り替えること。
• dequeの使い方しらべる。

今スタックの上下が入れ替わっているか、
色が反転している状態か。
というのを記憶しながら、dequeでシミュレーションした。

ソース

int solve(deque<int> &S){
  bool revS = false, revC = false;
  int cnt = 0;
  while(!S.empty()){
    int now;
    if(revS){
      now = S.back();
      S.pop_back();
    }
    else {
      now = S.front();
      S.pop_front();
    }
    if(revC){
      if(now == 0)now = 1;
      else now = 0;
    }
    if(now == 0){
      revS = !revS;
    }
    else {
      revC = !revC;
      cnt++;
    }
  }
  return cnt;
}

class MathContest {
public:
  int countBlack(string B, int R) {
    deque<int> S(B.size() * R);
    rep(i, R){
      rep(j, B.size()){
        int b=0;
        if(B[j] == 'B')b = 1;
        S[i*B.size() + j] = b;
      }
    }
    int result = solve(S);
    return result;
  }
};