AtCoderの Typical DP Contestを解いてみた (D サイコロ)

今回もTypical DP Contestのアウトプットに関する記事です.

今回解いた問題はD サイコロです

前回までの記事は以下の通りです.

1. A コンテスト
2. B ゲーム
3. C トーナメント

D サイコロ

今回は「D サイコロ」という問題を解きました.

問題の概要

サイコロを回振ったとき、出た目の積がの倍数となる確率を求めよ.

解法

今回はサイコロを一回振ったときに、の値しか取らないことに着目します.

(ここに気づけたら本問題の9割は解けたようなもんだと思っています.)

の値をそれぞれ素因数分解すると、素因数としてはの3つしか出現しません.

したがって、これらの値の積で表される値の素因数ものみです.

要するに、サイコロを回振ったときの出目の積をとすると $$ P_N = 2^{a} * 3^{b} * 5^{c} $$ で表すことができます.

逆に、7以上の素因数を含む値はサイコロの出目の積で表すことができません.

以上のことから、今回はサイコロを回振ったときに素因数の個数で場合分けをして漸化式を作っていきます.

$$ \begin{cases} dp[n + 1][a][b][c] += \frac{dp[n][a][b][c]}{6} & (n + 1回目に1が出たとき) \\ dp[n + 1][a + 1][b][c] += \frac{dp[n][a][b][c]}{6} & (n + 1回目に2が出たとき) \\ dp[n + 1][a][b + 1][c] += \frac{dp[n][a][b][c]}{6} & (n + 1回目に3が出たとき) \\ dp[n + 1][a + 2][b][c] += \frac{dp[n][a][b][c]}{6} & (n + 1回目に4が出たとき) \\ dp[n + 1][a][b][c + 1] += \frac{dp[n][a][b][c]}{6} & (n + 1回目に5が出たとき) \\ dp[n + 1][a + 1][b + 1][c] += \frac{dp[n][a][b][c]}{6} & (n + 1回目に6が出たとき) \\ \end{cases} $$ 例えば、回目にが出たときは素因数の個数が個増えるので、となります.

また、初期値は、、最終出力は、です.

実装上の注意

サイコロの出目が4のとき素因数2の個数が2つ増えます.

これはに相当しますが、のときにの部分が配列の範囲を超えてしまうので、 $$ dp[n + 1][min(a + 2, A)][b][c] $$ と上限を超えないように制御しています.

他の出目のときも同じようにしています.

ソース

使用言語はC++です.

#include <iostream>
#include <string>
#include <vector>
#include <cstdlib>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <map>
#include <stack>
#include <queue>
#include <set>
#include <cstring>

using namespace std;
// ascending order
#define vsort(v) sort(v.begin(), v.end())
// descending order
#define vsort_r(v) sort(v.begin(), v.end(), greater<int>())
#define vunique(v) unique(v.begin(), v.end())
#define mp make_pair
#define ts(x) to_string(x)
#define rep(i, a, b) for(int i = (int)a; i < (int)b; i++)
#define repm(i, a, b) for(int i = (int)a; i > (int)b; i--)
#define bit(a) bitset<8>(a)
typedef long long ll;
typedef pair<int, int> P;
const ll INF = 1e18;

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);

    int N;
    ll D;
    cin >> N >> D;

    int A, B, C;
    A = B = C = 0;
    while(D % 2 == 0) {A++; D /= 2;}
    while(D % 3 == 0) {B++; D /= 3;}
    while(D % 5 == 0) {C++; D /= 5;}

    if(D != 1) {cout << 0 << endl; return 0;}

    long double p = 1.0 / 6.0;
    long double dp[N + 1][A + 1][B + 1][C + 1];
    memset(dp, 0, sizeof(long double) * (N + 1) * (A + 1) * (B + 1) * (C + 1));
    dp[0][0][0][0] = 1;
    rep(n, 0, N) {
        rep(a, 0, A + 1) {
            rep(b, 0, B + 1) {
                rep(c, 0, C + 1) {
                    dp[n + 1][a][b][c] += p * dp[n][a][b][c];
                    dp[n + 1][min(a + 1, A)][b][c] += p * dp[n][a][b][c];
                    dp[n + 1][a][min(b + 1, B)][c] += p * dp[n][a][b][c];
                    dp[n + 1][min(a + 2, A)][b][c] += p * dp[n][a][b][c];
                    dp[n + 1][a][b][min(c + 1, C)] += p * dp[n][a][b][c];
                    dp[n + 1][min(a + 1, A)][min(b + 1, B)][c] += p * dp[n][a][b][c];
                }
            }
        }
    }

    cout << dp[N][A][B][C] << endl;

}