#14933 (C++11) No.162 8020運動

• 問題: No.162 8020運動
• ユーザー: koyumeishi
• 提出日時: 2015-03-06 01:07:36
• 言語: C++11 (gcc 13.3.0)
• 結果: AC
• 実行時間: 109 ms / 5,000 ms
• コード長: 1,692 bytes
• コンパイル時間: 639 ms
• コンパイル使用メモリ: 79,300 KB
• 実行使用メモリ: 6,944 KB
• 最終ジャッジ日時: 2024-06-24 09:52:20
• 合計ジャッジ時間: 3,490 ms
• ジャッジサーバーID （参考情報）: judge3 / judge5

ファイルパターン	結果
sample	AC * 3
other	AC * 26

ソースコード

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
#include <iostream>
#include <vector>
#include <cstdio>
#include <sstream>
#include <map>
#include <string>
#include <algorithm>
#include <queue>
#include <cmath>
#include <set>
using namespace std;
// probability s -> t
double prob(vector<int>& P, int s, int t, int len){
    s <<= 1;
    t <<= 1;
    if( (s|t) > s ) return 0.0;
    double ret = 1.0;
    int mask = 0b111;
    for(int i=1; i<=len; i++){
        if( (s&(1<<i)) == 0 ) continue;
        int my_s = ( s>>(i-1) ) & mask;
        if( my_s == 0b010 ){
            if( (t&(1<<i)) == 0){
                ret *= P[0] * 0.01;
            }else{
                ret *= 1 - P[0] * 0.01;
            }
        }else if( my_s == 0b111 ){
            if( (t&(1<<i)) == 0){
                ret *= P[2] * 0.01;
            }else{
                ret *= 1 - P[2] * 0.01;
            }
        }else{
            if( (t&(1<<i)) == 0){
                ret *= P[1] * 0.01;
            }else{
                ret *= 1 - P[1] * 0.01;
            }
        }
    }
    return ret;
}
double dfs(vector<int>& P, vector<vector<double>>& memo, int s, int len, int y){
    if(memo[y][len] >= 0) return memo[y][len];
    if(y==0){
        return len;
    }
    //部分集合列挙
    double ret = 0.0;
    int sub = s;
    do{
        double p = prob(P, s, sub, len);
        double E_ = 0.0;
        int last_len = 0;
        for(int i=0; i<len; i++){
            if((sub >> i) & 1){
                last_len++;
            }else{
                E_ += dfs(P, memo, (1<<last_len)-1, last_len, y-1);
                last_len = 0;
            }
        }
        if(last_len > 0){
            E_ += dfs(P, memo, (1<<last_len)-1, last_len, y-1);
            last_len = 0;
        }
        ret += E_ * p;
        sub = (sub-1) & s;
    }while( sub != s );
    memo[y][len] = ret;
    return ret;
}
int main(){
    int A;
    cin >> A;
    vector<int> P(3);
    cin >> P[0] >> P[1] >> P[2];
    vector<vector<double>> memo(25, vector<double>(15, -1));
    double ans = dfs(P,memo, (1<<14)-1, 14, 80-A) * 2;
    printf("%.10f\n", ans);
    return 0;
}
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX