SRM459 Div2 Hard(1000) ParkAmusement

ParkAmusement

足場iからちょうどKステップでEにたどり着く確率をP[i]とするとベイズの定理から、足場iからスタートした確率はP[i]/ΣP[i]。

#include <string>
#include <vector>
#include <algorithm>
#include <numeric>

using namespace std;

class ParkAmusement
{
public:
    double getProbability( vector <string> landings, int startLanding, int K );
};

double ParkAmusement::getProbability( vector <string> landings, int startLanding, int K )
{
    int n = (int)landings.size();

    //  i番目の足場からKステップでEに到達する確率
    vector<double> P( n );
    for ( int i=0; i<n; i++ )
        P[i] = landings[i][i]=='E' ? 1 : 0;

    for ( int k=0; k<K; k++ )
    {
        vector<double> t = P;

        for ( int i=0; i<n; i++ )
        {
            int c = count( landings[i].begin(), landings[i].end(), '1' );
            P[i] = 0;
            for ( int j=0; j<n; j++ )
                if ( landings[i][j] == '1' )
                    P[i] += t[j] / c;
        }
    }

    return P[startLanding] / accumulate(P.begin(),P.end(),0.0);
}