結果

問題 No.162 8020運動
ユーザー krotonkroton
提出日時 2015-03-05 16:42:38
言語 C++11
(gcc 11.4.0)
結果
AC  
実行時間 831 ms / 5,000 ms
コード長 1,455 bytes
コンパイル時間 1,243 ms
コンパイル使用メモリ 148,668 KB
実行使用メモリ 92,832 KB
最終ジャッジ日時 2023-09-06 13:46:01
合計ジャッジ時間 23,376 ms
ジャッジサーバーID
（参考情報） 		judge15 / judge12
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 423 ms
92,720 KB
testcase_01 AC 615 ms
92,724 KB
testcase_02 AC 717 ms
92,588 KB
testcase_03 AC 814 ms
92,556 KB
testcase_04 AC 814 ms
92,560 KB
testcase_05 AC 831 ms
92,700 KB
testcase_06 AC 829 ms
92,624 KB
testcase_07 AC 802 ms
92,728 KB
testcase_08 AC 801 ms
92,612 KB
testcase_09 AC 431 ms
92,708 KB
testcase_10 AC 716 ms
92,728 KB
testcase_11 AC 624 ms
92,780 KB
testcase_12 AC 508 ms
92,728 KB
testcase_13 AC 810 ms
92,560 KB
testcase_14 AC 452 ms
92,640 KB
testcase_15 AC 447 ms
92,608 KB
testcase_16 AC 540 ms
92,592 KB
testcase_17 AC 467 ms
92,704 KB
testcase_18 AC 785 ms
92,704 KB
testcase_19 AC 688 ms
92,588 KB
testcase_20 AC 730 ms
92,768 KB
testcase_21 AC 736 ms
92,724 KB
testcase_22 AC 718 ms
92,728 KB
testcase_23 AC 725 ms
92,832 KB
testcase_24 AC 701 ms
92,588 KB
testcase_25 AC 742 ms
92,708 KB
testcase_26 AC 424 ms
92,780 KB
testcase_27 AC 622 ms
92,832 KB
testcase_28 AC 799 ms
92,620 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

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

const int SIZE = (1 << 14) + 10;

double dp[100][SIZE];
double P[5];

vector<pair<int,double>> nexts[SIZE];

void precalc(){
    for(int init=0;init<1<<14;init++){
        int mask = init << 1;
        int sub = mask;
        do {
            double p = 1;

            for(int i=1;i<=14;i++)if((mask >> i) & 1){
                int type = 0;
                if((mask >> (i - 1)) & 1)++type;
                if((mask >> (i + 1)) & 1)++type;

                if((sub >> i) & 1){
                    // 生き残る
                    p *= 1 - P[type];
                } else {
                    // 死ぬ
                    p *= P[type];
                }
            }

            nexts[init].push_back(make_pair(sub >> 1, p));
            sub = (sub - 1) & mask;
        } while(sub != mask);
    }
}

double solve(int A, int mask){
    double &res = dp[A][mask];
    if(res >= -0.5)return res;

    res = 0;
    if(A >= 80){
        for(int i=0;i<14;i++){
            if((mask >> i) & 1)++res;
        }
        return res;
    }

    for(auto ps : nexts[mask]){
        res += ps.second * solve(A + 1, ps.first);
    }

    return res;
}

int main(){
    memset(dp, -1, sizeof(dp));

    int A;
    cin >> A;

    cin >> P[0] >> P[1] >> P[2];
    P[0] /= 100;
    P[1] /= 100;
    P[2] /= 100;

    precalc();

    int init = (1 << 14) - 1;
    printf("%.10f\n", 2 * solve(A, init));

    return 0;
}
0