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; } };