結果

問題 No.76 回数の期待値で練習
ユーザー なおなお
提出日時 2014-11-24 02:42:36
言語 C++11
(gcc 11.4.0)
結果
AC  
実行時間 19 ms / 5,000 ms
コード長 1,178 bytes
コンパイル時間 1,108 ms
コンパイル使用メモリ 158,724 KB
実行使用メモリ 11,392 KB
最終ジャッジ日時 2024-06-10 22:01:39
合計ジャッジ時間 1,556 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge2
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 19 ms
11,264 KB
testcase_01 AC 19 ms
11,392 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#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