Codeforces Round #301 (Div. 2) D. Bad Luck Island

問題

Problem - 540D - Codeforces

解法

適切にメモ化再帰する。
以下ソースコード

double dp[111][111][111][3];

vector<double> dfs(int r, int s, int p) {
    if ((r==0 && s == 0) || (s==0 && p==0) || (p==0 && r==0)) {
        vector<double> ret(3);
        if (r) ret[0] = 1;
        if (s) ret[1] = 1;
        if (p) ret[2] = 1;
        for (int i = 0; i < 3; i++) {
            dp[r][s][p][i] = ret[i];
        }
        return ret;
    }
    if (dp[r][s][p][0] >= 0) {
        vector<double> ret(3);
        for (int i = 0; i < 3; i++) ret[i] = dp[r][s][p][i];
        return ret;
    }
    vector<double> ret(3);
    int zentai = r*s + s*p + p*r;
    // r vs s
    if (r > 0 && s > 0) {
        double P = (1. * r * s) / zentai;
        auto q = dfs(r, s-1, p);
        for (int i = 0; i < 3; i++) {
            ret[i] += P*q[i];
        }
    }
    // s vs p
    if (s > 0 && p > 0) {
        double P = (1. * s * p) / zentai;
        auto q = dfs(r, s, p-1);
        for (int i = 0; i < 3; i++) {
            ret[i] += P*q[i];
        }
    }
    // p vs r
    if (p > 0 && r > 0) {
        double P = (1. * p * r) / zentai;
        auto q = dfs(r-1, s, p);
        for (int i = 0; i < 3; i++) {
            ret[i] += P*q[i];
        }
    }
    for (int i = 0; i < 3; i++) {
        dp[r][s][p][i] = ret[i];
    }
    return ret;
}

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    int r, s, p;
    cin >> r >> s >> p;
    for (int i = 0; i < 111; i++) for (int j = 0; j < 111; j++) for (int k = 0; k < 111; k++) for (int l = 0; l < 3; l++) dp[i][j][k][l] = -1;
    dfs(r, s, p);
    printf("%.15lf %.15lf %.15lf\n", dp[r][s][p][0], dp[r][s][p][1], dp[r][s][p][2]);
    return 0;
}