結果

問題 No.76 回数の期待値で練習
コンテスト
ユーザー なお
提出日時 2014-11-24 02:42:36
言語 C++11（廃止可能性あり）
(gcc 13.3.0 + boost 1.89.0)
結果
AC  
実行時間 19 ms / 5,000 ms
コード長 1,178 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 1,695 ms
コンパイル使用メモリ 155,924 KB
実行使用メモリ 11,520 KB
最終ジャッジ日時 2025-01-02 21:07:10
合計ジャッジ時間 1,888 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 2
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define REP(i, n)           for(int(i)=0;(i)<(n);++(i))
#define REPEAT(i, k, n)     for(int(i)=(k);(i)<((k)+(n));++(i))
#define EPS 1e-9

double dp[1001000];
double dice[6];

double ans[] = {
    1.0000000000000000,
    1.0833333333333333,
    1.2569444444444444,
    1.5353009259259260,
    1.6915991512345676,
    2.0513639724794235,
};

int main(){
    // ダイスの目の確率を二分探索
    dice[5] = 1;
    REP(k,5){
        double a = 0, b = 1;
        while(abs(a-b) > EPS){
            double c = (a+b)/2; dice[k] = c;
            REP(i,k+2){
                double r = 0;
                REP(j,6) if(i-j >= 0) r += dp[i-j]*dice[j];
                dp[i+1] = r + 1;
            }
            if(dp[k+2] < ans[k+1]) a = c; else b = c;
        }
        dice[5] -= dice[k];
    }

    // DP
    REP(i,1000000){
        double r = 0;
        REP(j,6) if(i-j >= 0) r += dp[i-j]*dice[j];
        dp[i+1] = r + 1;
    }

    int T;
    cin >> T;
    REP(i,T){
        int N;
        cin >> N;
        printf("%.8f\n", dp[N]);
    }
    return 0;
}
0