TCO11 Round1 Medium(500) MuddyRoad
MuddyRoad
.MMMMM.という部分があるとMの個数をmとして、⌊m/2⌋回泥を踏む。それぞれの区間について、.MMMMM.の形になる確率を求めて足し合わせる。
#include <vector> using namespace std; class MuddyRoad{public: double getExpectedValue( vector <int> road ) { int n = (int)road.size(); vector<double> P(n); for ( int i=0; i<n; i++ ) P[i] = road[i]/100.; double ans = 0; for ( int i=0; i<n; i++ ) for ( int j=i+1; j<n; j++ ) { double p = (1-P[i])*(1-P[j]); for ( int k=i+1; k<=j-1; k++ ) p *= P[k]; ans += ((j-i-1)/2)*p; } return ans; }};