結果

問題 No.162 8020運動
ユーザー krotonkroton
提出日時 2015-03-05 16:42:38
言語 C++11
(gcc 13.3.0)
結果
AC  
実行時間 903 ms / 5,000 ms
コード長 1,455 bytes
コンパイル時間 1,414 ms
コンパイル使用メモリ 162,448 KB
実行使用メモリ 93,104 KB
最終ジャッジ日時 2024-06-24 08:18:41
合計ジャッジ時間 24,765 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 26
権限があれば一括ダウンロードができます

ソースコード

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