yukicoder No.58 イカサマなサイコロ
問題概要
省略
解法
dpで解いた。
dp1[i][j] := 太郎君がサイコロをi回振って、合計がjの時の確率
dp2[i][j] := 次郎君がサイコロをi回振って、合計がjの時の確率
とおいて、漸化式でi=1からi=nまでループを回して埋めていった。
漸化式は単純で、いかさまサイコロの時は、4~6それぞれの目が出る確率が、1/3なので、
dp1[i][j] += dp1[i - 1][j - k] / 3.0
上の式は、i回目にk(4~6)の目がでたときで、i-1回目までの合計がj-kでi回目にkがでて、合計がkになるときの確率を計算している。kがでる確率は1/3なので、i-1回目に合計j-kの時の確率を3で割っている。
普通のさいころの場合は、1~6の目がそれぞれ、1/6の確率で出るので、6で割ればいい。
確率dpのDAG上の動きは以下のスライドのp38からがとてもわかりやすい。
www.slideshare.net
このスライド見る感じ、今回の問題は、わざわざdpを2次元にしなくても、そのままの状態でDAGだから、1次元で行けるってことだよね?
また今回の問題は、誤差許容が甘いので、モンテカルロ法を実装しても通る。
ミス
確率dpを勉強するのに役立った。確率dpはDAGが意識しやすい? ほかの人のコード見てたら、dpを1次元分だけで、配るdp書いてた人が結構いたけど、jを大きいほうから小さいほうに回していて、よくわからない。なにやってるんだ?dpで配列使いまわすの苦手だからどうにかしないと。
コード
確率dp
#include <iostream> #include <cstdio> typedef long long ll; using namespace std; #define rep(i,n) for(int i=0;i<(n);i++) int n, k; //dp1[i][j] := 太郎君がサイコロをi回振って、合計がjの時の確率 //dp2[i][j] := 次郎君がサイコロをi回振って、合計がjの時の確率 double dp1[20][150], dp2[20][150]; //何通りあるかで調べる int main(void){ cin >> n >> k; rep(i, 20)rep(j, 150) dp1[i][j] = dp2[i][j] = 0; dp1[0][0] = 1.0; dp2[0][0] = 1.0; //太郎 for (int i = 1; i <= n; ++i){ for (int j = 1; j <= 6 * i; ++j){ if(i <= k){ for (int k = 4; k <= 6; ++k){ if(j - k >= 0){ dp1[i][j] += dp1[i - 1][j - k] / 3.0; // printf("1 dp1[%d][%d] = %d\n", i, j, dp1[i][j]); } } }else{ for (int k = 1; k <= 6; ++k){ if(j - k >= 0){ dp1[i][j] += dp1[i - 1][j - k] / 6.0; // printf("2 dp1[%d][%d] = %f\n", i, j, dp1[i][j]); } } } } } //次郎 for (int i = 1; i <= n; ++i){ for (int j = 1; j <= 6 * i; ++j){ for (int k = 1; k <= 6; ++k){ if(j - k >= 0){ dp2[i][j] += dp2[i - 1][j - k] / 6.0; // printf("3 dp2[%d][%d] = %f\n", i, j, dp2[i][j]); } } } } double ans = 0; for (int sum1 = 1; sum1 <= n * 6; ++sum1){//太郎の合計 for (int sum2 = 0; sum2 < sum1; ++sum2){//次郎の合計 //太郎の合計がsum1で次郎の合計がsum2 (< sum1)の時の確率を足しお合わせる ans += dp1[n][sum1] * dp2[n][sum2]; } } printf("%.9f\n", ans); return 0; }
#include <iostream> #include <algorithm> #include <vector> #include <cstdio> #include <cstdlib> typedef long long ll; using namespace std; #define rep(i,n) for(int i=0;i<(n);i++) int n, k; bool solve(){//モンテカルロ法 int sum_taro = 0; rep(i, k){ sum_taro += rand() % 3 + 4; } rep(i, n - k){ sum_taro += rand() % 6 + 1; } int sum_ziro = 0; rep(i, n){ sum_ziro += rand() % 6 + 1; } if(sum_taro > sum_ziro) return true; else return false; } int main(void){ cin >> n >> k; int win = 0; rep(i, 4000000){ if(solve()) win++; } printf("%.9f\n", (double)win / 4000000.0); return 0; }