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;
}};