cafelier@SRM

TCO Round1 500

あとで | 11:21 |

わーいDPだ

class KthProbableElement {
public:
  double probability(int M, int lowerBound, int upperBound, int N, int K) 
  {
    double dp1[101][101]={0}, dp2[101][101], (*P)[101]=dp1, (*Q)[101]=dp2;

    P[0][0] = 1.0;
    for(int i=0; i<M; ++i)
    {
      memset( Q, 0, sizeof(double)*101*101 );
      for(int a=0; a<=i; ++a)
        for(int b=0; a+b<=i; ++b)
        {
          Q[a+1][b] += P[a][b] * (N-lowerBound) / (upperBound-lowerBound+1);
          Q[a][b+1] += P[a][b] * 1 / (upperBound-lowerBound+1);
          Q[a][b]   += P[a][b] * (upperBound-N) / (upperBound-lowerBound+1);
        }
      swap(P, Q);
    }

    double p = 0.0;
    for(int a=0; a<=M; ++a)
      for(int b=0; a+b<=M; ++b)
        if( a<K && K<=a+b )
          p += P[a][b];
    return p;
  }
};

P[a][b] @ i == M個中i個目まで値を選んだとき、N未満の値がa個、Nがb個、(Nより大きいのがi-a-b個)、になっている確率。なんでこれが時間内で書けないかな自分は…