srm 504 mid MathContest

問題

http://www.topcoder.com/stat?c=problem_statement&pm=11233&rd=14433

• 黒と白の玉が一列に並んでいる。
• 先頭から順番に取り出す。
• 取り出した玉が
  • 白なら、残った玉の順番をひっくり返す
  • 黒なら、玉の色を反転させる。

方針

基本的には、素直に調べる。但し、取り出す度に、色を反転させたり順番を反転させたりするのは面倒なので、当初の順番と逆順か？当初の色と反転しているか？を保持するフラグを持っておいて、deque(先頭と末尾から取り出せるキュー)で処理。

回答例

#include <sstream>
#include <string>
#include <vector>
#include <map>
#include <algorithm>
#include <iostream>
#include <utility>
#include <set>
#include <cctype>
#include <queue>
#include <stack>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <iterator>


using namespace std;


class MathContest{
public:
  bool color_invert;
  bool stack_revert;
  deque<bool> dq;

  char get_out(){
    char out;
    if(stack_revert){
      out = dq.back();
      dq.pop_back();
    }
    else{
      out = dq.front();
      dq.pop_front();
    }
    if(color_invert){
      out = !out;
    }
    return out;
  }

  int countBlack(string ballSequence, int repetitions){
    dq.resize(ballSequence.size() * repetitions);
    for(int i = 0; i < repetitions; i++){
      for(size_t j = 0; j < ballSequence.size(); j++){
	dq[i * ballSequence.size() + j] = (ballSequence[j] == 'B');
      }
    }

    color_invert = false;
    stack_revert = false;
    int ret = 0;
    char out;
    while(dq.size() > 0){
      out = get_out();
      if(out){
	color_invert = !color_invert;
	ret++;
      }
      else{
	stack_revert = !stack_revert;
      }
    }
    return ret;
  }



};