SRM472 Div2 Hard(1000) RectangularIsland

RectangularIsland

問題サイズが小さければDPで簡単に求められるが、この問題だと時間が足りない。横方向と縦方向の移動を分けて考える。sステップ横方向に動いたあと島に居る確率をp_h(s)、縦方向をp_v(s)とする。steps回の移動のうち、ちょうどi回横方向に動く確率は_stepsC_i/2^steps。上下からも左右からも落ちなければ島に居られるので、答えは、
　　Σ_i=0^steps_stepsC_i/2^steps p_h(i) p_v(steps-i)。

#include <vector>
#include <numeric>
#include <cmath>

using namespace std;

class RectangularIsland
{
public:
    double theProbablity( int width, int height, int x, int y, int steps );
};

double RectangularIsland::theProbablity( int width, int height, int x, int y, int steps )
{
    vector<double> ph( steps + 1 );     //  横方向にi回移動した時、島に居る確率
    vector<double> pv( steps + 1 );     //  縦方向にi回移動した時、島に居る確率
    vector<double> island;

    //  横
    island = vector<double>( width+2, 0 );
    island[x+1] = 1;

    for ( int s=0; s<=steps; s++ )
    {
        ph[s] = accumulate( island.begin()+1, island.end()-1, 0.0 );

        vector<double> temp = island;
        for ( int i=1; i<width+1; i++ )
            island[i] = ( temp[i-1] + temp[i+1] ) / 2;
    }

    //  縦
    island = vector<double>( height+2, 0 );
    island[y+1] = 1;

    for ( int s=0; s<=steps; s++ )
    {
        pv[s] = accumulate( island.begin()+1, island.end()-1, 0.0 );

        vector<double> temp = island;
        for ( int i=1; i<height+1; i++ )
            island[i] = ( temp[i-1] + temp[i+1] ) / 2;
    }

    //
    double p = 0;

    for ( int i=0; i<=steps; i++ )
    {
        double t = pow( 2.0, -steps );
        for ( int j=0; j<i; j++ )
            t *= (double)( steps - j ) / ( j + 1 );

        p += t * ph[i] * pv[steps-i];
    }

    return p;
}