SRM504 Div1 Easy(250), Div2 Medium(500) MathContest

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;
}};