SRM488 Div1 Easy(250) TheBoredomDivOne

動的計画法。退屈ではない人がi人の場合に全員を退屈にする時間の期待値をb_i、その時に退屈ではない人をj人選ぶ確率をp_jとすると、

b_i = p₀ b_i + p₁ b_i-1 + p₂ b_i-2 + 1。

変形して、

b_i = ( p₁ b_i-1 + p₂ b_i-2 + 1 ) / (1-p₀)。

#include <vector>

using namespace std;

class TheBoredomDivOne{public:
double find( int n, int m )
{
    vector<double> b(m+2);

    b[0] = b[1] = 0;
    for ( int i=1; i<=m; i++ )
    {
        int total = (n+m)*(n+m-1)/2;
        double p0 = (double)(n+m-i)*(n+m-i-1)/2 / total;
        double p1 = (double)i*(n+m-i) / total;
        double p2 = (double)i*(i-1)/2 / total;

        b[i+1] = ( p1*b[i] + p2*b[i-1] + 1 ) / (1-p0);
    }

    return b[m+1];
}};