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]

が分かる。

あとは、実装するだけ。

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りまくってますけど・・・。