[AtCoder] ABC 184 D – increment of coins

2020年11月23日2020年12月12日

問題

方針

\( d(i, j, k) \) を金貨が \( i \) 枚、銀貨が \( j\) 枚、銅貨が \( k \) 枚であるときの確率とします。初期値は、\( d(A, B, C) = 1 \) で、その他は \( 0 \) で初期化します。ここで、\( d(i, j, k) \) の遷移先を考えます。ある操作で、増える硬貨は \( 1 \) 種類なので、

\begin{eqnarray}
d(i + 1, j, k) &\leftarrow& d(i + 1, j, k) + \dfrac{i}{i + j + k} d(i, j, k)\\
d(i, j + 1, k) &\leftarrow& d(i, j + 1, k) + \dfrac{j}{i + j + k} d(i, j, k)\\
d(i, j, k + 1) &\leftarrow& d(i, j, k + 1) + \dfrac{k}{i + j + k} d(i, j, k)
\end{eqnarray}

となります。したがって、答えは

\[ \sum_{i = 0}^{99} \sum_{j = 0}^{99} (100 + i + j – A – B – C)(d(100, i, j) + d(i, 100, j) + d(i, j, 100))\]

となります。

コード

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

double d[101][101][101]{};

int main() {
    int A, B, C;
    cin >> A >> B >> C;
    d[A][B][C] = 1.0;
    for (int i = A; i < 100; i++) {
        for (int j = B; j < 100; j++) {
            for (int k = C; k < 100; k++) {
                d[i + 1][j][k] += d[i][j][k] * (double) i / (i + j + k);
                d[i][j + 1][k] += d[i][j][k] * (double) j / (i + j + k);
                d[i][j][k + 1] += d[i][j][k] * (double) k / (i + j + k);
            }
        }
    }
    double ans = 0;
    int m = A + B + C;
    for (int i = 0; i < 100; i++) {
        for (int j = 0; j < 100; j++) {
            double k = 100 + i + j - m;
            ans += k * (d[100][i][j] + d[i][100][j] + d[i][j][100]);
        }
    }
    printf("%.9f\n", ans);
    return 0;
}