結果

問題 No.574 正多面体サイコロ
コンテスト
ユーザー rpy3cpp
提出日時 2017-10-07 16:19:38
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 2 ms / 2,000 ms
コード長 1,706 bytes
コンパイル時間 1,906 ms
コンパイル使用メモリ 169,476 KB
実行使用メモリ 6,820 KB
最終ジャッジ日時 2024-11-17 04:30:09
合計ジャッジ時間 2,478 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 20
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;

vector<double> calc_fac(int N){
    vector<double> fac(N + 1, 1.0);
    for (int i = 1; i <= N; ++i) fac[i] = fac[i - 1] * i;
    return fac;
}

vector<double> calc_p(double p, int N){
    vector<double> ps(N + 1, 1.0);
    for (int i = 0; i < N; ++i) ps[i + 1] = ps[i] * p;
    return ps;
}

double prob(int x, int F, int N, int K, const vector<double> & pM, const vector<double> & fac){
    // F面体をN回振って、K番目に大きい数字がxである確率
    // x+1以上の数字が出た回数が L回で、x-1以下の数字が出た回数がS回、xと等しい値が出た回数はM = N - L - S 回とする。
    // このとき、x が K番目に大きい数字となるためには、L, S が以下を満たすことが必要。
    // 0 <= L < K, and  K <= N - S and S >= 0
    // 0 <= L < K and 0 <= S <= N - K
    // このような目の出方が生じる確率は、
    // p(L, S) = ((F - x)/F)^L * ((x - 1)/F)^S * (1/F)^M * N!/(L! * S! * M!)
    auto pL = calc_p((F - x)*1.0/F, K);
    auto pS = calc_p((x - 1)*1.0/F, N - K + 1);
    double ret = 0.0;
    for (int L = 0; L < K; ++L){
        for (int S = 0; S <= N - K; ++S){
            int M = N - L - S;
            ret += pL[L] * pS[S] * pM[M] * fac[N] / fac[L] / fac[S] / fac[M];
        }
    }
    return ret;
}

double solve(int F, int N, int K){
    double ans = 0.0;
    auto pM = calc_p(1.0/F, N);
    auto fac = calc_fac(N);
    for (int x = 1; x <= F; ++x){
        ans += x * prob(x, F, N, K, pM, fac);
    }
    return ans;
}

int main() {
    int F, N, K;
    cin >> F >> N >> K;
    cout.precision(12);
    cout << fixed << solve(F, N, K) << endl;
    return 0;
}
0