CS Academy Ball Sampling
リンク : https://csacademy.com/contest/archive/task/ball-sampling/
問題概要
N色のボールがあり、箱にそれぞれA_i個入っている。同様に確からしいとき、すべての色のボールを一回以上取り出す期待値を求めよ。
解説
いわゆる、コンプリート問題と言われる、期待値と言えばの典型である。tsutajさんの下のスライドにとてもよくまとめられている。
http://compro.tsutajiro.com/archive/180220_probability_dp.pdf
dp[mask]を1回でも取った色の情報をmaskとして、maskから全色集めるまでの期待値とする。最終的な答えはdp[0]となる。
LL n, a[1100], sum; double dp[1 << 20]; int main() { cin >> n; rep(i, n) { cin >> a[i]; sum += a[i]; } Rrep(mask, (1LL << n)) { LL cur = 0; rep(i, n)if ((mask&(1LL << i)) == 0)cur += a[i]; double p = sum; p /= cur; rep(i, n) { if ((mask&(1LL << i)) == 0) { double q = a[i]; q /= cur; dp[mask] += (dp[mask | (1LL << i)] + p) * q; } } } printf("%.15f\n", dp[0]); return 0; }