WARush

SRMの結果とか、解けた問題のコードを書いていきます

SRM626 Div1 "FixedDiceGameDiv1"

問題

TopCoder Statistics - Problem Statement

アリスとボブはゲームで遊んでいた。アリスはb面体のサイコロをa回ふる。ボブはc面体のサイコロをd回ふる。n面体のそれぞれの面には1~nまでの数字が書かれている。

プレイヤーのスコアはサイコロをふって出た数の合計である。スコアが高いほうのプレイヤーが勝ちとなる。2人どちらも勝つ可能性がある。

あなたはint a, b, c, dが与えられる。すでに2人はサイコロをふり終えている。アリスが勝つ可能性がない場合、-1を返せ。そうでなければ、アリスとボブの具体的なスコアは分からないが、アリスがボブに勝ったとする。その時のアリスのスコアの期待値を返せ。

制約

1 <= a, b, c, d <= 50


考えたこと

得点ごとのふり方の数さえ分かればいけるな。

これは組み合わせ(nCm)かな?

んんっ?

重複組み合わせ(nHr)かなっ!?

あれ!!?

できない!

あれあれ~!!?

事後

DPでいけました。

dp[i][j] := i回サイコロを振ったときに、スコアがjとなる時の、サイコロのふり方の数

でやりました。


ソースコード

double A[55][2550];
double B[55][2550];

class FixedDiceGameDiv1 {
public:

    double getExpectation(int a, int b, int c, int d) {
        // A[i][j] := i回サイコロを振ったときに、スコアがjとなる時の、ふり方の数
        for (int i = 0; i < 55; i++) {
            for (int j = 0; j <= 2500; j++) {
                A[i][j] = B[i][j] = 0.0;
            }
        }
        for (int i = 1; i <= b; i++) {
            A[1][i] = 1;
        }
        for (int i = 1; i <= d; i++) {
            B[1][i] = 1;
        }
        for (int i = 1; i < a; i++) {
            for (int j = 1; j <= 2500; j++) {
                if (A[i][j] == 0.0) continue;
                for (int k = 1; k <= b; k++) {
                    A[i + 1][j + k] += A[i][j];
                }
            }
        }
        for (int i = 1; i < c; i++) {
            for (int j = 1; j <= 2500; j++) {
                if (B[i][j] == 0.0) continue;
                for (int k = 1; k <= d; k++) {
                    B[i + 1][j + k] += B[i][j];
                }
            }
        }

        // アリスがボブに勝つときの、ふり方の数とスコアの合計を算出
        double countSum = 0.0;
        double scoreSum = 0.0;        
        for (int my = 2; my <= 2500; my++) {
            for (int you = 1; you < my; you++) {
                countSum += A[a][my] * B[c][you];
                scoreSum += A[a][my] * B[c][you] * my;
            }
        }

        // 結果を返す。
        if (countSum == 0.0) return -1;
        return scoreSum / countSum;
    }
};