結果

問題 No.76 回数の期待値で練習
ユーザー codershifthcodershifth
提出日時 2015-08-04 01:46:35
言語 C++11
(gcc 11.4.0)
結果
AC  
実行時間 27 ms / 5,000 ms
コード長 3,407 bytes
コンパイル時間 1,144 ms
コンパイル使用メモリ 148,100 KB
実行使用メモリ 10,832 KB
最終ジャッジ日時 2023-09-25 00:58:06
合計ジャッジ時間 1,680 ms
ジャッジサーバーID
（参考情報） 		judge13 / judge15
このコードへのチャレンジ
（要ログイン）

テストケース

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

ソースコード

diff # 

#include <bits/stdc++.h>

typedef long long ll;
typedef unsigned long long ull;

#define FOR(i,a,b) for(int (i)=(a);i<(b);i++)
#define REP(i,n) FOR(i,0,n)
#define RANGE(vec) (vec).begin(),(vec).end()

using namespace std;

class CountExpectationPractice {
public:
    void solve(void) {
            int T;
            cin>>T;

            // sample から各目の出る確率を求めておく
            vector<double> ans = {0.0,
                                  1.0000000000000000,
                                  1.0833333333333333,
                                  1.2569444444444444,
                                  1.5353009259259260,
                                  1.6915991512345676,
                                  2.0513639724794235};

            // p[i] := i+1 が出る確率
            vector<double> p(6,0);

            // Nk がとりうる最大値
            int maxN = (int)(1E+6);

            // n が出るまでサイコロをふる回数の期待値
            vector<double> Exp(maxN+1,0);

            // Exp 更新関数
            // p が決定したものとみなして計算する。
            function<void(int)> update = [&](int n) {
                Exp[0] = 0;
                FOR(i,1,n+1)
                {
                    // k へは k-(j+1) 時点で j+1 の目を出したときに遷移するので
                    // Exp[k] = 1 + ∑ p[j]*Exp[k-(j+1)]
                    //             k>=j+1
                    Exp[i] = 1.0;
                    REP(j,6)
                        if (i-(j+1) >= 0)
                            Exp[i] += Exp[i-(j+1)] * p[j];
                }
            };

            // 二分探索で確立をもとめてやる
            // ans[k+2] ~ Exp[k+2] は k 番目までの p で確定するので先頭から順に二分探索で確定させていく
            // O(5*100*5) くらい
            REP(k,5)
            {
                // p = {p1,p2,...,p(k-1),0.0,...,0.0} として考える
                double l = 0.0;
                double u = 1.0;
                double mid = 0.0;

                // 確率的におかしなケースを計算させないように
                // 確定した p を使って探索範囲を絞る
                REP(i,k-1)
                    u -= p[i];

                REP(_,100)
                {
                    // p[k] を更新
                    p[k] = mid = (l+u)*0.5;
                    // p[0]+...+p[5] = 1.0 より p[5] は残りから計算できる
                    p[5] = 1.0;
                    REP(j,5)
                        p[5] -= p[j];

                    update(k+2); // Exp[k+2] までを更新

                    if (Exp[k+2] > ans[k+2])
                        u = mid;
                    else
                        l = mid;
                }
                p[k] = mid;
                p[5] = 1.0;
                REP(i,5)
                    p[5] -= p[i];
            }

            // p が確定したので最後の update
            update(maxN);

            REP(i,T)
            {
                int N;
                cin>>N;
                cout<<setprecision(20)<<Exp[N]<<endl;
            }
    }
};

#if 1
int main(int argc, char *argv[])
{
        ios::sync_with_stdio(false);
        auto obj = new CountExpectationPractice();
        obj->solve();
        delete obj;
        return 0;
}
#endif
0