Typical DP Contest D: サイコロ (動的計画法)
解法
サイコロを振った回数を1から少しずつ大きくしていく。それぞれの回数について、2の指数、3の指数、5の指数を数え、その状態になる確率を求める。
コード
import java.io.IOException; import java.util.Scanner; public class Main { public static void main(String[] arg) { Scanner sc = new Scanner(System.in); int N = sc.nextInt(); long D = sc.nextLong(); sc.close(); int[] count = new int[6]; int[] primes = { 2, 3, 5 }; for (int i = 0; i < primes.length; i++) { int p = primes[i]; while (D % p == 0) { D /= p; count[p]++; } } if (D != 1) { System.out.println(0); return; } double[][][] dp = new double[2 * N + 1][N + 1][N + 1]; dp[0][0][0] = 1; for (int n = 1; n <= N; n++) { for (int j2 = 2 * n; j2 >= 0; j2--) { for (int j3 = n; j3 >= 0; j3--) { for (int j5 = n; j5 >= 0; j5--) { if (j2 > 0) { dp[j2][j3][j5] += dp[j2 - 1][j3][j5]; } if (j3 > 0) { dp[j2][j3][j5] += dp[j2][j3 - 1][j5]; } if (j2 > 1) { dp[j2][j3][j5] += dp[j2 - 2][j3][j5]; } if (j5 > 0) { dp[j2][j3][j5] += dp[j2][j3][j5 - 1]; } if (j2 > 0 && j3 > 0) { dp[j2][j3][j5] += dp[j2 - 1][j3 - 1][j5]; } dp[j2][j3][j5] /= 6; } } } } double ans = 0; for (int i = 2 * N; i >= count[2]; --i) { for (int j = N; j >= count[3]; --j) { for (int k = N; k >= count[5]; --k) { ans += dp[i][j][k]; } } } System.out.println(ans); } static int nextInt() { int c; try { c = System.in.read(); while (c != '-' && (c < '0' || c > '9')) c = System.in.read(); if (c == '-') return -nextInt(); int res = 0; while (c >= '0' && c <= '9') { res = res * 10 + c - '0'; c = System.in.read(); } return res; } catch (IOException e) { // TODO Auto-generated catch block e.printStackTrace(); } return -1; } }