Yukicoder058 イカサマなサイコロ

問題概要

太郎君と二郎君はサイコロで勝負することになりました。
太郎君は普通の6面サイコロを$N$個、二郎くんは4,5,6が2つずつあるサイコロを$K$個、普通の6面サイコロを$N-K$個振る。
出目の多いほうが勝利するとき、太郎君が勝つ確率を求めよ。

$N,K\leqq10$

yukicoder058

解法

イカサマサイドは場合分けがあるけど、基本的には
$dp(i,sum):=i$個サイコロをふってその出目の合計値が$sum$になる確率
としてDPしてあげればよい。

サイコロの最大値をMとして、
計算量:$O(N^2*M^2)$

ソース

     #include <bits/stdc++.h>
     using namespace std;
     
     using VS = vector<string>;    using LL = long long;
     #define FOR(i, s, e) for (int(i) = (s); (i) < (e); (i)++)
     #define FORR(i, s, e) for (int(i) = (s); (i) > (e); (i)--)
     
     int main() {
       cin.tie(0);
       ios_base::sync_with_stdio(false);
     
       LL N, K;
       cin >> N >> K;
       vector<vector<double>>dpTaro(N + 1, vector <double>(61, 0));
       vector<vector<double>>dpJiro = dpTaro;
       dpJiro[0][0] = dpTaro[0][0] = 1;
     
       //Jiro
       FOR(i, 0, N) {
           FOR(d, 1, 6 + 1) {
               FORR(sum, 60, 0 - 1) {
                   dpJiro[i + 1][sum + d] += dpJiro[i][sum] / 6.0;
               }
           }
       }
     
       // Taro
       FOR(i, 0, N) {
           if (i < K) {
               FOR(d, 4, 6 + 1) {
                   FORR(sum, 60, 0 - 1) {
                       dpTaro[i + 1][sum + d] += 2.0*dpTaro[i][sum] / 6.0;
                   }
               }
           }
           else {
               FOR(d, 1, 6 + 1) {
                   FORR(sum, 60, 0 - 1) {
                       dpTaro[i + 1][sum + d] += dpTaro[i][sum] / 6.0;
                   }
               }
           }
       }
       double ans = 0;
       FOR(i, 0, 61) {
           FOR(j, 0, i) {
               ans += dpJiro[N][j] * dpTaro[N][i];
           }
       }
       cout << fixed << setprecision(10) << ans << "\n";
     
       return 0;
     }