AOJ 1286: Expected Allowance

はじめに

• 問題: http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1286
• ソースコード: http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=1364464
• Javaで実装

問題文概訳

ヒデユキは、彼の父ウジサトからお小遣いとして毎月千円札を何枚かもらえます。 毎月１日に、何枚の千円札がもらえるかを決定します。 父ウジサトはn個のm面ダイスを取り出し、整数kを宣言します。 ヒデユキはダイスを振ります。 もらえる千円札の枚数は、ダイスの目の和からkを引いた数字となります。 ただし、目の合計がkを超えていなかったとしても、 最低でも千円札1枚はもらえることになっています。 m面ダイスは、1からmまでの面があり、どの目が出るのも同様に確からしいとします。

あなたには、何枚の千円札がもらえるのか、期待値を計算してもらいます。

例えば、 の場合。 1, 2, 3, 4, 5, 6, 7, 8, 9 枚もらえる確率が、それぞれ 6/36, 2/36, ... , 2/36, 1/36 で期待値は4.111111...となります。

入力

が空白区切りで与えられます。 ただし、[tex: nm * mⁿ ＜ 10⁸] です。

入力の終わりは3つのゼロで表されます。

出力

期待値を一行に出力せよ。誤差は 10^-7 まで許容される。

方針

動的計画法で、dp[i][j] = i個サイコロを振って合計jになるパターンの数 となります。サイコロの目をmeとすると、dp[i+1][j+me] += dp[i][j] という感じでDPテーブルを更新していきます。

しかし、これではメモリを無駄に使っています。サイコロの目の合計値の最大は mn なので、DPテーブルは n * (mn) 程度のサイズになってしまいます。そこで、今回の場合、iについては、1回前の情報さえあれば十分なことがわかります。これを使えば、2 * (mn) 程度のサイズでOKとなります。問題文から、nmは 10⁸ を超えることはありません。

さて、肝心の更新処理にかかるオーダーですが、n回サイコロを降る * n*mマスのテーブルをなめる * m通りの目がある で n * n * m * m となります。n * m * mⁿ よりはだいぶ小さいので間に合うでしょう（曖昧）

ソースコード

• 入力を受け取るのに自作クラスを使っています

class Main extends MyUtil{
    // public static Graph g;
    public static void main(String[] args) throws Exception{
        while(true){
            // ここはただたんに n, m, k　を標準入力から受け取っているだけ
            int n = readIntMap(0);    // ダイスの数
            int m = readIntMap(1);    // ダイスの面の数
            int k = readIntMap(2);    // カット
            if(n == 0 && m == 0 && k == 0) break;

            // dp[][sum] = 合計sumとなるようなサイコロの出方
            // sumの最大値は m*n
            int[][] dp = new int[2][m*n+1];
            dp[0][0] = 1;
            
            // i回目のサイコロ
            for(int i = 0; i < n; i++){
                // i+1番目のテーブルを初期化
                for(int j = 0; j < m*n+1; j++) dp[(i+1)%2][j] = 0;
                
                // i回振って合計jで、i+1回目にhが出たとき
                for(int prev_sum = 0; prev_sum < n*m+1; prev_sum++){
                    if(dp[i%2][prev_sum] == 0) continue;
                    for(int me = 1; me <= m; me++){
                        dp[(i+1)%2][prev_sum + me] += dp[i%2][prev_sum];
                    }
                }
            }
            
            int sum = 0;
            for(int i = 0; i < n*m+1; i++){
                // 合計していくが、0以下にはならない
                sum += Math.max(1, i - k) * dp[n%2][i];
            }
            // 場合の数で割る
            System.out.println(sum / Math.pow(m, n));
        }
    }
}

余談

DPで解く場合は↓の問題と似ていると思う

yoshiki-utakata.hatenablog.com