SRM459 Div2 Hard(1000) 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); }