AOJ 1286: Expected Allowance 深さ優先探索で期待値を計算する

問題

Expected Allowance | Aizu Online Judge

サイコロの数n、サイコロ1つあたりの面の数m、削減量kが与えられる。サイコロを同時に振った時の合計値から削減量kを引いただけ金がもらえるが、その値が1未満の場合は1だけもらえる。この時の期待値を計算する。

解法

深さ優先探索でサイコロの目の合計値を出す。それぞれの合計値は同様に確からしいので、全て足してパターンの数mⁿで割ればそれが期待値になる。

コード

import java.io.IOException;
import java.util.Scanner;

public class Main {
    private static int diceNum;
    private static int sideNum;
    private static int cutback;

    public static void main(String[] args) throws IOException {
        Scanner scanner = new Scanner(System.in);
        while (true) {
            diceNum = scanner.nextInt();// サイコロの数
            sideNum = scanner.nextInt();// サイコロの面の数
            cutback = scanner.nextInt();// ピンハネ
            if (diceNum == 0) {
                scanner.close();
                break;
            }

            int dfs = dfs(0, 0);// 深さ優先探索
            double ans = dfs / Math.pow(sideNum, diceNum);
            System.out.println(ans);

        }

    }

    static int dfs(int sum, int depth) {
        if (depth < diceNum) {
            // 振ったサイコロの数がサイコロの数より少なかったら、もう一個振る
            int dfs = 0;
            for (int i = 1; i <= sideNum; i++) {
                dfs += dfs(sum + i, depth + 1);
            }

            /*
            * 返されてきた値を足していく。 それぞれの値は独立なので、全て足しあわせて順列の和で割れば期待値が出る。
            */
            return dfs;
        } else {
            // サイコロ全部振ったらその合計値を返す
            if (sum - cutback < 1) {
                return 1;
            } else {
                return sum - cutback;
            }
        }
    }
}