SRM 488 250pt : TheBoredomDivOne

問題概要

白い玉がN個、黒い玉がM個ある。この中からランダムに二つの玉を選んで白く塗る。全ての玉が白になるまでかかるに必要な回数の期待値を求める問題。

解法

よくある一次方程式型のDPを解くだけ。

acceptされたコード

計算量O(M)。

const int MAX_N = 47;

double memo[MAX_N * 2 + 1];
bool visited[MAX_N * 2 + 1];


struct TheBoredomDivOne {

	double find(int n, int m) {
		return rec(n, m);
	}

	double rec(int n, int m){
		if(m <= 0){
			return 0.0;
		}
		if(visited[m]){
			return memo[m];
		}
		visited[m] = true;

		double& ret = memo[m] = 0.0;

		const int total = n + m;
		double prob = 1.0 / (total * (total - 1) / 2);

		ret += ( n * m * prob * (1.0 + rec(n + 1, m - 1)));
		ret += ( (m * (m-1) / 2 * prob * (1.0 + rec(n + 2, m - 2))) );
		ret += ( (n * (n - 1) / 2 * prob));
		ret /= ( 1.0 - (n * (n - 1) / 2 * prob) );

		return ret;
	}
};