CodeChef Ciel and Battle Arena
解法
基本的に dp[va][vb][m] = (自分の残り HP が va で敵の残り HP が vb で残り MP が m である時の勝率)という DP で解けますが, いろいろ難しいところがあるので, ひとつずつやっていきます。
まず, 「引き分けならもう一回やり直し」というところがめんどくさいですが, 「引き分けの場合の勝率」を p として, dp します。dp[Va][Vb][M] = dp[0][0][*] = p となっているはずなので, p の値について二分探索することで, 正確な p を求めることが出来ます。
去年(というか一昨年)のこどふぇすのペアプロ?で iwi さんと診断人さんが PerfectlyFairGame(確かそんな問題名だった気がする) を解いている時, iwi さんが「引き分けならやり直しでもこの問題は解ける」みたいなことを言っていた記憶があるのですが, 多分同じ手法ですかね。
あと, 素直に dp[i][j][k] を更新していくと, 一つの要素を更新するのに O(Sa*Sb) かかりますが, これは時間的にあやしいというか TLE しました。
そこで, 長方形の区間和を求めるのと同じノリで, (i-Sb, j-Sa) から (i, j) までの区間和を O(1) で求めるために, dpSum[i][j][k] = (dp[-100][-100][k] から dp[i][j][k] までの和) みたいなものを求めておきます。
const int B = 111; double dp[2*B][2*B][6]; double dpSum[2*B][2*B][6]; double getSum(int x1, int y1, int x2, int y2, int m) { return dpSum[x2+B][y2+B][m]-dpSum[x1-1+B][y2+B][m]-dpSum[x2+B][y1-1+B][m]+dpSum[x1-1+B][y1-1+B][m]; } int main() { int VA, VB, M; int Sa, Sb; while (cin >> VA >> VB >> Sa >> Sb >> M) { double low = 0, high = 1; for (int i = 0; i < 25; i++) { double med = (high+low)/2; for (int i = 0; i < 2*B; i++) for (int j = 0; j < 2*B; j++) for (int k = 0; k < 11; k++) dpSum[i][j][k] = 0; for (int i = 1; i <= B; i++) for (int j = 1; j <= B; j++) for (int m = 0; m <= M; m++) { dp[i][j][m] = med; dpSum[i][j][m] = dpSum[i-1][j][m] + dpSum[i][j-1][m] - dpSum[i-1][j-1][m] + dp[i][j][m]; } for (int i = B+1; i < 2*B; i++) for (int j = 1; j <= B; j++) for (int m = 0; m <= M; m++) { dp[i][j][m] = 1; dpSum[i][j][m] = dpSum[i-1][j][m] + dpSum[i][j-1][m] - dpSum[i-1][j-1][m] + dp[i][j][m]; } for (int i = 1; i <= B; i++) for (int j = B+1; j < 2*B; j++) for (int m = 0; m <= M; m++) { dp[i][j][m] = 0; dpSum[i][j][m] = dpSum[i-1][j][m] + dpSum[i][j-1][m] - dpSum[i-1][j-1][m] + dp[i][j][m]; } for (int m = 0; m <= M; m++) for (int Va = 1; Va <= VA; Va++) for (int Vb = 1; Vb <= VB; Vb++) { double& ret = dp[Va][Vb][m]; ret = 0; for (int i = 0; i <= m; i++) { int va = Va, vb = Vb; for (int j = 0; j < i; j++) { va = (va+1)/2; vb = (vb+1)/2; } double prob = 0; if (i == 0) { prob = getSum(va-Sb, vb-Sa, va-1, vb, m-i) + getSum(va-Sb, vb-Sa, va, vb-1, m-i) - getSum(va-Sb, vb-Sa, va-1, vb-1, m-i); prob /= (Sa+1)*(Sb+1)-1; } else { prob = getSum(va-Sb, vb-Sa, va, vb, m-i); prob /= (Sa+1)*(Sb+1); } ret = max(ret, prob); } dpSum[Va+B][Vb+B][m] = dpSum[Va-1+B][Vb+B][m] + dpSum[Va+B][Vb-1+B][m] - dpSum[Va-1+B][Vb-1+B][m] + ret; } if (dp[VA][VB][M] < med) high = med; else low = med; } printf("%.10lf\n", (high+low)/2); } return 0; }