正多面体サイコロ [yukicoder No.574] - はまやんはまやんはまやん

解法

https://yukicoder.me/submissions/208247

K番目に出る数について全探索して考えてみる。
K番目にxが来る時の確率をどうやって計算するか考えてみよう。
　
K番目にxが来ることを考える場合は出る数は「xより大きい数」「x」「xより小さい数」の3つについて考えれば良い。
それぞれi個,j個,k個出たとすると、i＜K, K≦i+jを満たしていればK番目にxが来ることが分かる。
そのため、(i,j,k)についても全探索して確率を求めていこう。
k=N-(i+j)であるため、全探索するのは(i,j)だけで良い。
　
各確率は以下のように計算できる
「xより大きい数」がでる確率 p1 = (F-x)/F
「x」がでる確率 p2 = 1/F
「xより小さい数」がでる確率 p3 = 1 - (p1 + p2)
よって、(x,i,j,k)の時の確率はp1^i*p2^j*p3^k*(数が出る順番の組み合わせ数)
ここで数が出る順番の組み合わせ数はN!/(i!*j!*k!)
　
これを全て計算してxと掛けると、K番目にxが出る場合の期待値が得られるので、これの総和を取ると答え。

int F, N, K;
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> F >> N >> K;

    double ans = 0;

    rep(x, 1, F + 1) {
        double p1 = (double)(F - x) / (double)F;
        double p2 = 1.0 / (double)F;
        double p3 = 1 - (p1 + p2);

        double p = 0;
        rep(i, 0, K) rep(j, 0, N - i + 1) {
            if (i + j < K) continue;
            int k = N - (i + j);

            // より大きい数がi回、同じ数がj回、より小さい数がk回
            double pp = 1;
            rep(a, 0, i) pp *= p1;
            rep(a, 0, j) pp *= p2;
            rep(a, 0, k) pp *= p3;
            rep(a, 0, N) pp *= (a + 1);
            rep(a, 0, i) pp /= (a + 1);
            rep(a, 0, j) pp /= (a + 1);
            rep(a, 0, k) pp /= (a + 1);

            p += pp;
        }
        ans += x * p;
    }

    printf("%.10f\n", ans);
}