Codeforces Round #301 Div2 D: Bad Luck Island (動的計画法)

問題

codeforces.com

解法

(r,s,p)から(r-1,s,p),(r,s-1,p),(r,s,p-1)に遷移するので、渡すDPを書く。

コード

import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
	Scanner sc = new Scanner(System.in);
	int R = sc.nextInt();
	int S = sc.nextInt();
	int P = sc.nextInt();
	sc.close();

	double[][][] dp = new double[R + 1][S + 1][P + 1];
	dp[R][S][P] = 1.0;
	for (int r = R; r >= 0; r--) {
	    for (int s = S; s >= 0; s--) {
		for (int p = P; p >= 0; p--) {
		    int all = r * s + s * p + p * r;
		    if (all == 0) {
			continue;
		    }
		    if (r > 0) {
			dp[r - 1][s][p] += dp[r][s][p] * r * p / all;
		    }
		    if (s > 0) {
			dp[r][s - 1][p] += dp[r][s][p] * r * s / all;
		    }
		    if (p > 0) {
			dp[r][s][p - 1] += dp[r][s][p] * s * p / all;
		    }
		}
	    }
	}

	double rock = 0.0;
	for (int i = 0; i <= R; i++) {
	    rock += dp[i][0][0];
	}

	double scissor = 0.0;
	for (int i = 0; i <= S; i++) {
	    scissor += dp[0][i][0];
	}

	double paper = 0.0;
	for (int i = 0; i <= P; i++) {
	    paper += dp[0][0][i];
	}

	System.out.println(rock + " " + scissor + " " + paper);

    }
}