Search on the blog

2011年3月15日火曜日

SRM BrushUp: BirdsCounting (435 div2 Hard)

鳥がn匹いる。
毎日ランダムにm匹の鳥を捕まえて、印を付ける。
x日後に、印が付いた鳥がy匹になる確率を求める。

実際の問題:

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


0 件のコメント:

コメントを投稿