SRM460 Div1 Medium(500) TheFansAndMeetingsDivOne

TheFansAndMeetingsDivOne

まず、JohnとBrusのそれぞれがl人のファンに会う確率を動的計画法で求める。Johnがi番目までの街の中からj個の街を訪れてl人のファンに会う確率をpJ_i,j,lとすると、
pJ_i,0,0 = 1
pJ_i,0,l = 0　(l>0)
pJ_i,j,l = Σ[m=minJ[i-1],maxJ[i-1] ] pJ_i-1,j-1,l-m s + pJ_i-1,j,l(1-s)。
ここで、sはj番目の街を訪れる確率で、s=j/i。
ファンの人数が一致する確率は、pJ_n,k・pB_n,k。

#include <vector>
#include <numeric>

using namespace std;

class TheFansAndMeetingsDivOne
{
    vector<double> fan( vector<int> minf, vector<int> maxf, int k );
public:
    double find( vector <int> minJ, vector <int> maxJ, vector <int> minB, vector <int> maxB, int k );
};

double TheFansAndMeetingsDivOne::find( vector <int> minJ, vector <int> maxJ, vector <int> minB, vector <int> maxB, int k )
{
    vector<double> pJ = fan( minJ, maxJ, k );
    vector<double> pB = fan( minB, maxB, k );

    int m = (int)min( pJ.size(), pB.size() );

    return inner_product( pJ.begin(), pJ.begin()+m, pB.begin(), 0.0 );
}

//  k個の街を訪れてi人のファンに会う確率の配列を返す
vector<double> TheFansAndMeetingsDivOne::fan( vector<int> minf, vector<int> maxf, int k )
{
    int n = (int)minf.size();
    int lm = accumulate( maxf.begin(), maxf.end(), 0 );

    //  [i][j][l]　i番目までの街のうちj個の街に訪れてl人のファンに会う確率
    static double p[41][41][40*40+1];

    for ( int i=0; i<=n; i++ )
    for ( int j=0; j<=i; j++ )
    for ( int l=0; l<=lm; l++ )
    {
        if ( j == 0 )
        {
            p[i][j][l] = l==0 ? 1 : 0;
        }
        else
        {
            double s = (double)j / i;       //  j番目の街を訪れる確率
            double *f = p[i-1][j-1] + max( l-maxf[i-1],   0 );
            double *t = p[i-1][j-1] + max( l-minf[i-1]+1, 0 );

            p[i][j][l] = accumulate(f,t,0.0) / (maxf[i-1]-minf[i-1]+1) * s
                       + p[i-1][j][l] * (1-s);
        }
    }

    return vector<double>( p[n][k], p[n][k]+lm+1 );
}