SRM504 Div1 Easy(250), Div2 Medium(500) MathContest
取り出す度に残りのボールの色や向きを反転せずに、これまでに取り出したボールの個数の偶奇で、取り出す位置を変えたりボールの色を反転するようにすればO(n)になる。
#include <string> using namespace std; class MathContest{public: int countBlack( string ballSequence, int repetitions ) { string s; for ( int i=0; i<repetitions; i++ ) s += ballSequence; int n = (int)s.size(); int top = 0; int bottom = n-1; int w = 0; int b = 0; for ( int i=0; i<n; i++ ) { char c; if ( w%2==0 ) c = s[top++]; else c = s[bottom--]; if ( b % 2 == 1 ) c = 'B'+'W'-c; if ( c == 'B' ) b++; else w++; } return b; }};