Typical DP Contest D: サイコロ (動的計画法)

問題

D: サイコロ - Typical DP Contest | AtCoder

解法

サイコロを振った回数を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;
	}

}