SRM475 Div1 Easy(300), Div2 Medium(550) 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; }