AOJ 1056 Ben Toh - lan496の日記

n日までに得る弁当の総数の期待値を計算すればいいわけだが、漸化式がうまく作れない && 他の人のコードを読んでも自明のようにdpしていてよく分からない、というツラさがあったので、この問題の漸化式が私のように漸化式が思いつかなかった人のために愚直に式の導出をする(もっとスマートに立式できる方法があったら教えて下さい)。

$E_n$ : n日までに得る弁当の総数
$F_n$ : n日目に弁当を得る確率
$G_{n,k}$ : n日目に弁当を得て、それまでにk-1回連続で弁当を得ている確率

期待値の性質から $E_n=\sum_{i=1}^n F_i$ なので、 $F_n$ の漸化式を求めればよい。

ここで $G_{n,k}(1 \leq k \leq n)$ について以下の漸化式が成り立つ。
$\displaystyle G_{n,k}=G_{n-1,k-1} \times \frac{1}{2^{k-1}} \ (1 \leq k < n) \\ G_{n,1}=1-F_n$
上式を繰り返し用いて、
$\displaystyle G_{n,k}=...=G_{n-k+1,1} \times \prod_{i=1}^{k-1} \frac{1}{2^i}=G_{n-k+1,1} \times 2^{-\frac{k(k-1)}{2}}$
ゆえに、
$\displaystyle G_{n,k} = \begin{cases} (1-F_{n-k})2^{-\frac{k(k-1)}{2}} & (1 \leq k < n) \\ 2^{-\frac{n(n-1)}{2}} & (k=n) \end{cases}$
ここで、 $F_{n}=\sum_{i=1}^n G_{n,i}$ であるから $n \geq 2$ のとき、
$\displaystyle F_n = 2^{-\frac{n(n-1)}{2}} + \sum_{i=1}^{n-1}{(1-F_{n-k}) 2^{-\frac{k(k-1)}{2}}}$
$F_1=1$ であるから、これで $F_n$ を逐次的に求めることができる。

解答の上では $2^{\frac{k(k-1)}{2}}$ がdouble型の有効桁数よりも小さい範囲で和を取れば十分である。

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

#define REP(i,n) for(int i=0;i<(int)(n);i++)

double memo[100001]={};

double cff(int k){
    if(k>=20) return 0.0;
    return pow(2.0,-k*(k-1)/2);
}

double dp(int n){
    if(n==1) return memo[1]=1.0;
    if(memo[n]>1e-10) return memo[n];
    double res=cff(n);
    for(int k=1;k<=min(n-1,20);k++){
        res+=(1-dp(n-k))*cff(k);
    }
    return memo[n]=res;
}

int main(){
	int n;
    while(cin >> n && n){
        double res=0;
        for(int i=1;i<=n;i++) res+=dp(i);
        cout << fixed << setprecision(10) << res << endl;
    }
	return 0;
}