srupのメモ帳

競プロで解いた問題や勉強したことを記録していくメモ帳

yukicoder No.58 イカサマなサイコロ

yukicoder 確率dp dp 確率 モンテカルロ法 私的良問

問題

問題概要

省略

解法

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