SRM460 Div1 Medium

500
dp_table[いくつまで見た][いくつ選んだ][ファンの合計]

dp_table[a+1][b][c] += dp_table[a][b][c] * 選ばれない確率
dp_table[a+1][b+1][c+d] += dp_table[a][b][c] * 選ばれる確率 * d人選ぶ確率

class TheFansAndMeetingsDivOne {
public:
  double find(vector <int> minJ, vector <int> maxJ, vector <int> minB, vector <int> maxB, int K) {

    const int SUM = 40 * 40 + 1;

    static double t[41][41][SUM];
    static double s[41][41][SUM];

    fill( &t[0][0][0], &t[40][40][SUM], 0 );
    fill( &s[0][0][0], &s[40][40][SUM], 0 );

    s[0][0][0] = t[0][0][0] = 1.0;

    const int N = minJ.size();

    for(int i=0; i<N; ++i){
      for(int j=0; j<=K; ++j){
        for(int k=0; k<SUM; ++k){

          const double P = (double)(K - j) / (double)(N - i);

          for(int l=minJ[i]; l<=maxJ[i]; ++l){
            if( SUM <= k + l )break;
            t[i+1][j+1][k+l] += t[i][j][k] * P / (maxJ[i] - minJ[i] + 1.0);
          }
          t[i+1][j][k] += t[i][j][k] * (1.0 - P);

          for(int l=minB[i]; l<=maxB[i]; ++l){
            if( SUM <= k + l )break;
            s[i+1][j+1][k+l] += s[i][j][k] * P / (maxB[i] - minB[i] + 1.0);
          }
          s[i+1][j][k] += s[i][j][k] * (1.0 - P);

        }
      }
    }


    double sum = 0;
    for(int i=0; i<SUM; ++i){
      sum += t[N][K][i] * s[N][K][i];
    }
    
    return sum;
  }

};