SRM475 Div1 Easy(300), Div2 Medium(550) RabbitStepping

RabbitStepping

全探索でも間に合う。が、こんな計算をする必要は無いらしい。Practiceのwriterの解答が美しすぎる。

#include <iostream>
#include <string>
#include <vector>

using namespace std;

class RabbitStepping
{
    int countbit( int n );
public:
    double getExpected( string field, int r );
};

double RabbitStepping::getExpected( string field, int r )
{
    int N = (int)field.size();

    int rabbit = 0;
    int total = 0;

    for ( int b=0; b<1<<N; b++ )
    if ( countbit( b ) == r )
    {
        vector<int> fl( N, 0 );     //  左からきた兎の数
        vector<int> fr( N, 0 );     //  右からきた兎の数

        for ( int i=0; i<N; i++ )
            if ( ( b & 1<<i ) != 0 )
                fl[i] = 1;
        
        for ( int n=N; n>=2; n-- )
        {
            vector<int> tl = fl;
            vector<int> tr = fr;
            fl = fr = vector<int>( N, 0 );

            for ( int i=0; i<n; i++ )
            {
                if ( i == 0 )
                    fl[i+1] += tl[i] + tr[i];
                else if ( i == n-1  ||  i == n-2 )
                    fr[i-1] += tl[i] + tr[i];
                else
                {
                    if ( field[i] == 'W' )
                        fr[i-1] += tl[i] + tr[i];
                    if ( field[i] == 'B' )
                        fl[i+1] += tl[i] + tr[i];
                    if ( field[i] == 'R' )
                        fr[i-1] = tl[i],
                        fl[i+1] = tr[i];
                }
            }

            for ( int i=0; i<n; i++ )
                if ( fr[i] + fl[i] >= 2 )
                    fr[i] = fl[i] = 0;
        }

        rabbit += fr[0] + fr[1] + fl[0] + fl[1];
        total++;
    }

    return (double)rabbit / total;
}

int RabbitStepping::countbit( int n )
{
    n = ( n & 0x55555555 ) + ( n >> 1 & 0x55555555 );
    n = ( n & 0x33333333 ) + ( n >> 2 & 0x33333333 );
    n = ( n & 0x0f0f0f0f ) + ( n >> 4 & 0x0f0f0f0f );
    n = ( n & 0x00ff00ff ) + ( n >> 8 & 0x00ff00ff );
    n = ( n & 0x0000ffff ) + ( n >>16 & 0x0000ffff );
    return n;
}