[yukicoder] No.58 イカサマなサイコロ - 山傘のプログラミング勉強日記

問題

No.58 イカサマなサイコロ - yukicoder

f:id:yamakasa3:20180608030207p:plain

$N$ 個のサイコロの出目の和を計算して、値が相手より大きければ勝ちとなります。ただし、こちらのサイコロは出目が異なるものを $K$ 個使います。

考え方

愚直に計算します。

$n$ 個のサイコロの目の和の組み合わせ

$S(n, k)$ をサイコロが $n$ 個のときに和の合計が $k$ となる組み合わせの数とします。このとき、 $k$ が取り得る値の範囲は、

$n \leq k \leq 6n$

となります。ここで、 $S(n, k)$ を $S(n - 1, \cdot)$ を用いて表すことを考えます。 $n$ 個のサイコロの目の合計が $k$ になるためには、 $n - 1$ 個の出た目の和 $s_{n - 1}$ が、

$k - 6 \leq s_{n-1} \leq k - 1$

となっていなければなりません。したがって、

$S(n, k) = S(n - 1, k - 1) + S(n - 1, k - 2) + S(n - 1, k - 3)$ $+ S(n - 1, k - 4) + S(n - 1, k - 5) + S(n - 1, k - 6)$

となります。この漸化式を解くことで個のサイコロの目の和の組み合わせが得られます。

出目が異なる $n$ 個のサイコロの目の和の組み合わせ

出る目の数が $4, 5, 6$ なので、上記と同様にして考えると、

$S(n, k) = S(n - 1, k - 4) + S(n - 1, k - 5) + S(n - 1, k - 6)$

となります。

確率の計算

場合の数が求められたら後は確率を計算します。 $d$ を場合の数の合計とします。普通のサイコロであれば、 $d = 6^{N}$ となります。イカサマなサイコロを含むほうでは、 $d = 6^{N - K}\times 3^{K}$ となります。

$S(N, k) / d$ は $n$ 個のサイコロの和が $k$ となる確率となります。

この確率を元に相手の合計より自分の合計が大きくなる確率を足し合わせていけばよいです。

コード

import java.util.Arrays;
import java.util.Scanner;

public class Exec0058 {
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int N = scan.nextInt();
        int K = scan.nextInt();
        scan.close();
        int a[] = new int[6 * N + 1];
        int b[] = new int[6 * N + 1];
        int [][]S = new int[N + 1][6 * N + 1];


        Arrays.fill(a, 0);
        Arrays.fill(b, 0);
        for(int i = 1; i <= 6; i++) {
            a[i] = 1;
            S[1][i] = 1;
        }
        for(int i = 2; i <= N; i++) {
            for(int j = i; j <= 6 * i; j++) {
                for(int k = 1; k <= 6; k++) {
                    if(j - k <= 0) {
                        break;
                    }
                    S[i][j] += S[i - 1][j - k];
                }
            }
        }
        if(K==0) {
            long d = 0;
            d = (long)Math.pow(6, N);
            double ans = 0;
            for(int i = N; i <= 6 * N; i++) {
                for(int j = N; j < i; j++) {
                    ans += (double)S[N][i] / d * (double) S[N][j] / d;
                }

            }
            System.out.println(ans);
            System.exit(0);
        }

        int[][]S2 = new int[N + 1][6 * N + 1];
        for(int i = 1; i <= 6; i++) {
            if(i <= 3) {
                S2[1][i] = 0;
            }else {
                S2[1][i] = 1;
            }
        }
        for(int i = 2; i <= K; i++) {
            for(int j = i; j <= 6 * i; j++) {
                for(int k = 4; k <= 6; k++) {
                    if(j - k <= 0) {
                        break;
                    }
                    S2[i][j] += S2[i - 1][j - k];
                }
            }
        }
        if(N != K) {
            for(int i = K + 1; i <= N; i++) {
                for(int j = i; j <= 6 * i; j++) {
                    for(int k = 1; k <= 6; k++) {
                        if(j - k <= 0) {
                            break;
                        }
                        S2[i][j] += S2[i - 1][j - k];
                    }
                }
            }
        }
        long d1 = 0;
        long d2 = 0;
        for(int i = N; i <= 6 * N; i++) {
            d1 += S[N][i];
            d2 += S2[N][i];
        }

        double ans = 0;
        for(int i = N; i <= 6 * N; i++) {
            for(int j = N; j < i; j++) {
                ans += (double) S2[N][i] / d1 * S[N][j] /  d2;
            }

        }
        System.out.println(ans);
    }
}

感想

モンテカルロ法でも解けるのね。そんな・・・。

追記

モンテカルロ法による解法

import java.util.Scanner;

public class Exec0058a {
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int N = scan.nextInt();
        int K = scan.nextInt();
        scan.close();
        int p1;            //　普通のサイコロの和
        int p2;        // イカサマなサイコロの和
        int n = 1000000;  // シミュレーション回数
        int win = 0;  // p2の勝利数
        for(int i = 0; i < n; i++) {
            p1 = 0;
            p2 = 0;
            for(int j = 0; j < N; j++) {
                p1 += (int)(Math.random() * 6) + 1;
                if(j < K) {
                    p2 += (int)(Math.random() * 3) + 4;
                }else {
                    p2 += (int)(Math.random() * 6) + 1;
                }
            }
            if(p2 > p1) {
                win ++;
            }
        }
        double ans = (double) win / n;
        System.out.println(ans);
    }
}