SRM435 Div2 Hard

1000

dp[何日目][何匹にマークした]

最初は、2^20 * 2^20 * 5 が思い浮かんで絶望した。

view plainprint?

1. class BirdsCounting {  
2. public:  
3.   double computeProbability(int birds, int caught, int days, int marked)  
4.   {  
5.     const int B = 20 + 2;  
6.     const int D = 5 + 2;  
7.   
8.     double nCk[B][B];  
9.     fill(&nCk[0][0], &nCk[B][0], 0);  
10.     nCk[0][0] = 1;  
11.   
12.     for (int n = 1; n < B; ++n) {  
13.       nCk[n][0] = 1;  
14.       for (int k = 1; k < B; ++k) {  
15.         nCk[n][k] = nCk[n - 1][k - 1] + nCk[n - 1][k];  
16.       }  
17.     }  
18.   
19.     double dp[D][B];  
20.     fill(&dp[0][0], &dp[D][0], 0);  
21.     dp[0][0] = 1;  
22.   
23.     for (int d = 0; d < days; ++d) {  
24.       for (int b = 0; b <= birds; ++b) {  
25.         for (int i = 0; i <= caught; ++i) {  
26.           if (b + i <= marked) ; else continue;  
27.           if (0 <= caught - i) ; else continue;  
28.           double p = nCk[birds - b][i] * nCk[b][caught - i] / nCk[birds][caught];  
29.           dp[d + 1][b + i] += dp[d][b] * p;  
30.         }  
31.       }  
32.     }  
33.   
34.     return dp[days][marked];  
35.   }  
36. };  

class BirdsCounting {
public:
  double computeProbability(int birds, int caught, int days, int marked)
  {
    const int B = 20 + 2;
    const int D = 5 + 2;

    double nCk[B][B];
    fill(&nCk[0][0], &nCk[B][0], 0);
    nCk[0][0] = 1;

    for (int n = 1; n < B; ++n) {
      nCk[n][0] = 1;
      for (int k = 1; k < B; ++k) {
        nCk[n][k] = nCk[n - 1][k - 1] + nCk[n - 1][k];
      }
    }

    double dp[D][B];
    fill(&dp[0][0], &dp[D][0], 0);
    dp[0][0] = 1;

    for (int d = 0; d < days; ++d) {
      for (int b = 0; b <= birds; ++b) {
        for (int i = 0; i <= caught; ++i) {
          if (b + i <= marked) ; else continue;
          if (0 <= caught - i) ; else continue;
          double p = nCk[birds - b][i] * nCk[b][caught - i] / nCk[birds][caught];
          dp[d + 1][b + i] += dp[d][b] * p;
        }
      }
    }

    return dp[days][marked];
  }
};