SRM 504 Div2 Medium MathContest

問題

次のようなゲームを行う.
白と黒のボールがスタックに積まれている.
・スタックのトップを取り出し,捨てる
・取り出したボールが白なら新しいスタックに詰め替える.(スタックの順番を変える)
・取り出したボールが黒なら中のボールの色を反転させる.
・ボールがある限りこの作業を繰り返す.
スタックの初期値と繰り返し階数が与えられた時黒のボールが取り出される回数を答えよ.

解答

2番めのスタックの詰替えは取り出す位置がトップからボトムに切り替わったと考えれば,わざわざすべての要素の順番を入れ替えなくても良い.また黒の取り出し回数,白の取り出し回数を覚えておけば,初期値のスタックの中身をいじることなく,今どの位置からボールを取り出し,またその色が何色なのか分かる.
後はシミュレーションするだけ.

class MathContest {
public:
  int countBlack(string ballSequence, int repetitions) {
    int res = 0;
    int n = ballSequence.size();
    bool turn = false;
    bool reverse = false;
    int top = 0;
    int bottom = n * repetitions - 1;
	while((bottom - top) >= 0){
      bool black = false;
      if(reverse){
        if(ballSequence[bottom % n] == 'B') black = true;
        // cout << ballSequence[bottom % n];
        bottom--;
      }else{
        if(ballSequence[top % n] == 'B') black = true;
        // cout << ballSequence[top % n];
        top++;
      }

      if(turn) black = !black;
      // if(black) cout << "B";
      // else cout << "W";

      if(black){ turn = !turn; res++;}
      else reverse = !reverse;
    }
    cout << endl;
    return res;
  }
};