SRM BrushUp: BirdsCounting (435 div2 Hard)

鳥がn匹いる。

毎日ランダムにm匹の鳥を捕まえて、印を付ける。

x日後に、印が付いた鳥がy匹になる確率を求める。

実際の問題：

http://www.topcoder.com/stat?c=problem_statement&pm=10243&rd=13697

典型的なDP。

d日後にi匹の鳥に印が点いている確率をdp[d][i]とおくと、

dp[d][i] = dp[d-1][i-m] * comb[i-m][0] * comb[n-i+m][m] / comb[n][m]

+ dp[d-1][i-m+1] * comb[i-m+1][1] * comb[n-i+m-1][m-1] / comb[n][m]

+ .....

+ dp[d-1][i] * comb[i][m] * comb[n-i][0] / comb[n][m]

が分かる。

あとは、実装するだけ。

view plainprint?

1. double dp[8][32];  
2. int comb[32][32];  
3. class BirdsCounting {  
4. public:  
5.     double computeProbability(int birdsNumber, int caughtPerDay, int daysNumber, int birdsMarked) {  
6.         memset(dp, 0x00, sizeof(dp));  
7.         init();  
8.   
9.         dp[0][caughtPerDay] = 1.0;  
10.         for (int d = 1; d < daysNumber; d++) {  
11.             for (int i = 0; i < birdsNumber+1; i++) {  
12.                 for (int k = 0; k < caughtPerDay+1; k++) {  
13.                     dp[d][i+k] += dp[d-1][i] * prep(birdsNumber - i, k)  
14.                             * prep(i, caughtPerDay-k) / prep(birdsNumber, caughtPerDay);  
15.                 }  
16.             }  
17.         }  
18.   
19.         return dp[daysNumber-1][birdsMarked];  
20.     }  
21.   
22. private:  
23.     double prep(int n, int k) {  
24.         if (k > n)  
25.             return 0.0;  
26.   
27.         return comb[n][k];  
28.     }  
29.   
30.     void init() {  
31.         REP(i, 32) comb[i][0] = 1;  
32.         FOR (i, 1, 32) FOR (j, 1, 32)  
33.             comb[i][j] = comb[i-1][j] + comb[i-1][j-1];  
34.     }  
35.   
36. };  

double dp[8][32];
int comb[32][32];
class BirdsCounting {
public:
    double computeProbability(int birdsNumber, int caughtPerDay, int daysNumber, int birdsMarked) {
        memset(dp, 0x00, sizeof(dp));
        init();

        dp[0][caughtPerDay] = 1.0;
        for (int d = 1; d < daysNumber; d++) {
            for (int i = 0; i < birdsNumber+1; i++) {
                for (int k = 0; k < caughtPerDay+1; k++) {
                    dp[d][i+k] += dp[d-1][i] * prep(birdsNumber - i, k)
                            * prep(i, caughtPerDay-k) / prep(birdsNumber, caughtPerDay);
                }
            }
        }

        return dp[daysNumber-1][birdsMarked];
    }

private:
    double prep(int n, int k) {
        if (k > n)
            return 0.0;

        return comb[n][k];
    }

    void init() {
        REP(i, 32) comb[i][0] = 1;
        FOR (i, 1, 32) FOR (j, 1, 32)
            comb[i][j] = comb[i-1][j] + comb[i-1][j-1];
    }

};

Div.2 Hard、Div.1 Middleレベルがようやく解けるようになってきた感じがする。

本番ではhogeりまくってますけど・・・。