mayoko’s diary

プロコンとかいろいろ。

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