問題
白か黒で塗られているボールが入ったスタックが与えられる。「上からボールを1個を取り出し、黒だったら残りのボールを全て色反転、白だったら残りのボールの順序を反転し、取り出したボールは捨てる」という操作を繰り返したとき、黒いボールを取り出す回数はいくらか。
解法
制約が緩いのでシミュレーションする。順序反転や色反転は、どちらから見るかという方向やカウントするべき色を保持することでで行える。
コード
#include"bits/stdc++.h" using namespace std; using ll = long long; class MathContest { public: int countBlack(string ballSequence, int repetitions) { string all; for (int i = 0; i < repetitions; i++) { all += ballSequence; } enum { FRONT, BACK }; int pop_dir = FRONT; char count_color = 'B'; int ans = 0; const auto size = all.size(); for (int i = 0; i < size; i++) { auto pop_ball = (pop_dir == FRONT ? all.front() : all.back()); (pop_dir == FRONT ? all.erase(0, 1) : all.erase(all.size() - 1)); if (pop_ball == count_color) { ans++; count_color = (count_color == 'B' ? 'W' : 'B'); } else { pop_dir = (pop_dir == FRONT ? BACK : FRONT); } } return ans; } };