Codeforces Round #301 Div2 D: Bad Luck Island (動的計画法)
解法
(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); } }