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; } };