Codeforces #265 Div1 D. World of Darkraft - 2

本番はB,Cを通した時点でHackしてたけど、これこんな簡単に書けるのか。
http://codeforces.com/contest/464/problem/D

問題

初期状態でLV1の道具がK個ある。
ここで以下の処理をN回行う。

• K個のうち1個を等確率でランダムに選択する。
• 選択した道具のレベルをtとする。ここで新たに1～(t+1)のいずれかのレベルの道具が等確率で1個登場する。
• 既に持っている道具と新しく登場した道具について、レベルの高い方を手元に残し、低い方を片方売ると、そのレベル分のお金が手に入る。

得られる金額の期待値はいくらか。

解法

1個分の道具について考える。
レベルtの道具を持っているとき、新たな道具のレベルが1～tならそれを売り、(t+1)なら交換して手持ちのものを売ると良い。
この時得られるお金の期待値は(t+2)/2-1/(t+1)である。

ここでK個の道具のレベルがそれぞれで…と考える必要はなく、全体でどのレベルの道具がどんな確率で保持しているかを保持すればよい。
あるレベルtの道具の保持率をP[t]とすると、1回処理を行った結果は：以下のようになる。

• (t+1)の道具を引き当てP[t+1]が増加する確率：P[t]*(1/(j+1)/K)
• t以下の道具を引き当てP[t]が残る確率：P[t]*(1-1/(j+1)/K)

Kで割っているのは、(t+1)の道具を引き当ててもレベルが上がるのは1個分の武器だけだからである。

このままだとO(NK)の計算となるが、レベルがある程度上がるとP[t]は無視できるレベルに小さいので、レベル上限は700程度で計算しておけばよい。

double dp[2][1000];
int N,K;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>K;
	dp[0][1]=1;
	double ret=0;
	FOR(i,N) {
		int cur=i%2,tar=cur^1;
		ZERO(dp[tar]);
		FOR(j,1000) if(dp[cur][j]>=1e-100) {
			ret+=dp[cur][j]*((j+2)/2.0-1/(j+1.0));
			dp[tar][j]+=dp[cur][j]*(1-1.0/(j+1)/K);
			dp[tar][j+1]+=dp[cur][j]*1.0/(j+1)/K;
		}
	}
	_P("%.12lf\n",ret);
}

まとめ

わかってしまえば今回のCFで一番実装が軽い。