TopCoder SRM 825 : Div2 Hard RollAllOnes

まぁ典型問題ではある。
https://community.topcoder.com/stat?c=problem_statement&pm=17402

問題

N個のD面ダイスがある。
これらが、全部1の目になるまで以下を行う。

• 1が出ていないダイスを、一斉に転がす。(1が出ているダイスはこれ以上目が変わらない。)

全部1の目になるまでにかかる処理回数の期待値を求めよ。

解法

f(n) := 残りn個のダイスから初めて、全部1の目になるまでのダイスを転がす回数の期待値
とする。求めたいのはf(N)である。

g(n,m) := n個のダイスを転がしたとき、ちょうどm個が1の目を出す確率
とすると、1個以上1の目が出ると状態が遷移するので、
f(n) = 1/(1-g(n,0)) + sum(f(n-m)*g(n,m)/(1-g(n,0)))
で計算できる。g(n,m)はDPでも組み合わせでも容易に計算できる。

double dp[55];
double prob[55];

class RollAllOnes {
	public:
	double solve(int N, int D) {
		double p=1.0/D;
		double q=1-p;
		ZERO(dp);
		
		int i,x,y;
		
		for(i=1;i<=N;i++) {
			
			ZERO(prob);
			prob[0]=1;
			FOR(x,i) {
				for(y=i;y>=0;y--) {
					prob[y+1]+=prob[y]*p;
					prob[y]=prob[y]*q;
				}
			}
			double fail=prob[0];
			double success=1-fail;
			dp[i]+=1.0/success;
			for(x=1;x<=i;x++) {
				dp[i]+=prob[x]/success*dp[i-x];
			}
			cout<<i<<" "<<dp[i]<<endl;
		}
		return dp[N];
		
	}
}

まとめ

久々にDiv1Easy=Div2Mediumだったね。