YukiCoder No.162 - 8020運動
想定誤解法らしい.(システムテストに目をつけられたら落ちそう.)
解法
上下の歯は独立しているので,上の歯14本だけを考える.
あらかじめ,歯の状態間の遷移確率を計算しておく.
配るdp[年齢][歯の状態(bit表現)]をする.20・2^14・2^14(≒5.3x10^9)でΩ\・8・)チューンだが,実はΩ\・8・)チューンでもない.
1歳老いるときの配る回数を考える.ある歯の状態からの遷移先は2^(生存している歯の本数)個ある.
(生存しているそれぞれの歯に対して,生存させるか,させないかの2通りがあるから.)
なので,配る回数は
と表せる.
括弧内を落ち着いて見ると,「14個からk個選んで,それらに0,1のいずれかを入れる方法の総数」と解釈できる.
全体をゆったり眺めると,「14個のマスに0,1,つかわないのいずれかを割り当てる方法の総数」と解釈できる.これは14桁の3進数の個数,すなわち,3^14に等しい.
ゆえに配る回数の総数は20・3^14(≒9.5x10^7)となるので(前処理が重いので1[s]は超えるが)間に合う.
[追記(15/03/28 22:33)]
落ち着いて見なくても,ゆったり眺めなくても,2項定理から
と求められます.くろとんさんに教えていただきました.ありがとうございました.
[追記おわり]
コード
// Wrongri-La Shower #include <cstdio> #include <vector> typedef std::pair<int,double> Pair; double P[3]; // 虫歯に「なる」確率 std::vector<Pair> ns[1<<14]; double dp[21][1<<14]; double probability(int prev, int next){ double res = 1.0; for(int i=0;i<14;i++){ if(!(prev >> i & 1)){continue;} double p; if(i == 0){ p = P[prev >> 1 & 1]; }else if(i == 13){ p = P[prev >> 12 & 1]; }else{ p = P[(prev >> i-1 & 1) + (prev >> i+1 & 1)]; } res *= next >> i & 1 ? 1.0-p : p; } return res; } int main(){ int N; scanf("%d", &N); N = 80-N; scanf("%lf %lf %lf", P, P+1, P+2); for(int i=0;i<3;i++){P[i] /= 100;} for(int i=0;i<1<<14;i++){ for(int j=0;j<1<<14;j++){ if((i & j) != j){continue;} ns[i].push_back(std::make_pair(j, probability(i, j))); } } dp[0][(1<<14)-1] = 1.0; for(int i=0;i<N;i++){ for(int j=0;j<1<<14;j++){ for(const auto& p : ns[j]){ dp[i+1][p.first] += dp[i][j] * p.second; } } } double res = 0.0; for(int i=0;i<1<<14;i++){ res += dp[N][i] * __builtin_popcount(i); } printf("%.12f\n", res * 2); }