Millionaire(GCJ APAC Semifinal 2008)

#Millionaire(GCJ APAC Semifinal 2008)

先離散化，然後從最後一回合的勝率往前推，直到推到第一回合。

考慮最後一回合，有以下三種情況：

如果已經有錢 m, 1000000 <= m，則沒必要繼續賭下去，押注 0 元，可以以 1 的機率勝利。
如果已經有錢 m, 500000 <= m < 1000000，則將所有的錢都押注，勝率為p。雖然不一定需要賭上所有的錢，但既然非贏到 1000000 才算勝利，而且必需在這個回合取勝，輸掉的話一毛錢也沒有，那乾脆全下注了。
如果已經有錢 m, 0 <= m < 500000，則不可能取勝，機率為 0。

之後反推倒數第二回合：

以 M = 2, P = 0.75 為例：

區間(萬)	第一回合	第二回合
100+	1.000000	1.000000
[75, 100)		0.750000
[50, 75)		0.750000
[25, 50)		0.000000
[0, 25)		0.000000

假設我們要得出第一回合 [50, 75) 這個區間的勝率，因不確定在這一回合要下注多少，所以我們每個都試試，取最大值。

假設我們下注 0，則有
- （在這一回合獲勝）P 的機率在第二回合變成 [50, 75) 這個區間，
- （在這一回合輸掉）(1-P) 的機率在第二回合變成 [50, 75) 這個區間，
所以勝率是 P * possibility[2][[50, 75)] + (1-P) * possiblity[2][[50, 75)] = possibility[2][[50, 75)] = 0.750000
假設我們下注 (0 ~ 25]，則有
- （在這一回合獲勝）P 的機率在第二回合變成 [75, 100) 這個區間，
- （在這一回合輸掉）(1-P) 的機率在第二回合變成 [25, 50) 這個區間，
所以勝率是 P * possibility[2][[75, 100)] + (1-P) * possiblity[2][[25, 50)] = 0.750000 * 0.750000 + 0.250000 * 0.000000 = 0.562500。
假設我們下注 (25, 50)，則有
- （在這一回合獲勝）P 的機率在第二回合變成 100+ 這個區間，
- （在這一回合輸掉）(1-P) 的機率在第二回合變成 [0, 25) 這個區間，
所以勝率是 P * possibility[2][100+] + (1-P) * possiblity[2][[0, 25)] = 0.750000 * 1.000000 + 0.250000 * 0.000000 = 0.750000。
假設我們下注 全部，其結果與 3. 相同

在這四種可能中，最大的勝率為 0.750000，所以這一格就填入 0.750000。

根據這個方法，就能反推任何回合的任何區間了。同一個例子，最終結果如下：

區間(萬)	第一回合	第二回合
100+	1.000000	1.000000
[75, 100)	0.937500	0.750000
[50, 75)	0.750000	0.750000
[25, 50)	0.562500	0.000000
[0, 25)	0.000000	0.000000

最後只要看 X 在哪個區間就能知道要輸出那個區間的勝率了。

因區間有 2^M + 1 個，時間複雜度極高。所幸，M 不大，但編譯時仍需使用 -O3，這樣可以把執行時間從 3m 降到 30s。

Code

#include <iostream>
#include <algorithm>
#include <cstring>
#include <string>

using namespace std;

int M, X;
double P;

double dp[2][(1 << 15) + 1];

double solve() {
    int n = 1 << M;
    double *prev = dp[0];
    double *next = dp[1];
    memset(prev, 0, sizeof(double) * (n+1));

    prev[n] = 1.0;
    for (int r = 0; r < M; r++) {
        for (int i = 0; i <= n; i++) {
            int jub = min(i, n-i);
            double t = 0.0;
            for (int j = 0; j <= jub; j++) {
                t = max(t, P * prev[i+j] + (1-P) * prev[i-j]);
            }
            next[i] = t;
        }

        // printf("next: ");
        // for (int i = 0; i <= n; i++)
        //     printf("%.6f ", next[i]);
        // printf("\n");

        swap(prev, next);
    }

    int i = (long long) X * n / 1000000;
    return prev[i];
}

int main() {
    int N;
    cin >> N;

    for (int c=1; c<=N; c++) {
        cin >> M >> P >> X;
        printf("Case #%d: %.6f\n", c, solve());
    }

    return 0;
}

amoshyc/millionaire.md

Code