最初、「期待値の線形性」を使うのかなと思って迷走した... D は DP の D だった。

問題へのリンク

問題概要

袋の中に金貨が $A$ 枚、銀貨が $B$ 枚、銅貨が $C$ 枚入っている。袋の中にあるいずれかの種類の硬貨が 100 枚になるまで以下の操作を繰り返す。

操作：袋の中から硬貨をランダムに 1 枚取り出す
取り出した硬貨と同じ種類の硬貨を 2 枚袋に戻す

操作回数の期待値を求めよ。

制約

$0 \le A, B, C \le 99$
$A+B+C \ge 1$

考えたこと

最初、上手いこと「期待値の線形性」が使えるのかなと疑ったりして時間を喰ってしまった。機械的に DP すればよかった。

まずそもそも今回の問題において「袋の中の状態」としてあり得る場合の数がとても少ない。具体的には、最悪でも $100^{3}$ 通りになる。よって原理的には、何も考えなくても DP できそうなのだ。

${\rm dp} \lbrack a \rbrack \lbrack b \rbrack \lbrack c \rbrack$ := 袋の中の金貨、銀貨、銅貨の枚数がそれぞれ $a, b, c$ であるときの、残り操作回数の期待値

このように「残り回数の期待値」に関して DP する問題は、実は EDPC にもあるので、その経験があると、スムーズかもしれない！！

atcoder.jp

DP 遷移

さて、期待値の DP って難しいと感じている方が多いかもしれないけど、やることはめっちゃ単純。ただ単に、「次の手としてありうるもの」をそれぞれ打っていくだけ！！

${\rm dp} \lbrack a \rbrack \lbrack b \rbrack \lbrack c \rbrack$ を求めるためには、次の 3 パターンが考えられる。

金貨を選ぶとき

まず $a = 0$ のときはこの手は選べない。 $a \gt 0$ のときは、確率 $p_{A} = \frac{a}{a+b+c}$ でこの手が選ばれる。そして金貨を選ぶと、 $(a+1, b, c)$ の状態に遷移する。その状態からゴールするまでの回数の期待値は ${\rm dp} \lbrack a+1 \rbrack \lbrack b \rbrack \lbrack c \rbrack$ となる。

よって、金貨を選ぶときの期待値は

$\frac{a}{a+b+c} \times ({\rm dp} \lbrack a+1 \rbrack \lbrack b \rbrack \lbrack c \rbrack + 1)$

となる。「+１」は「金貨を選ぶ」という行為そのものを表している。

銀貨を選ぶとき

先ほどと同様に、銀貨を選ぶときの期待値は

$\frac{b}{a+b+c} \times ({\rm dp} \lbrack a \rbrack \lbrack b+1 \rbrack \lbrack c \rbrack + 1)$

となる。

銅貨を選ぶとき

先ほどと同様に、銅貨を選ぶときの期待値は

$\frac{c}{a+b+c} \times ({\rm dp} \lbrack a \rbrack \lbrack b \rbrack \lbrack c+1 \rbrack + 1)$

となる。

まとめ

以上をまとめると、次のようになる。

${\rm dp} \lbrack a \rbrack \lbrack b \rbrack \lbrack c \rbrack$
$= \frac{a}{a+b+c} \times ({\rm dp} \lbrack a+1 \rbrack \lbrack b \rbrack \lbrack c \rbrack + 1)$
$+ \frac{b}{a+b+c} \times ({\rm dp} \lbrack a \rbrack \lbrack b+1 \rbrack \lbrack c \rbrack + 1)$
$+ \frac{c}{a+b+c} \times ({\rm dp} \lbrack a \rbrack \lbrack b \rbrack \lbrack c+1 \rbrack + 1)$

計算量は $M = 100$ として、 $O(M^{3})$ となる。実装上は、ループでも、メモ化再帰でもできる。両方やってみる。

for 文ループによる実装

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

double dp[110][110][110];
int main() {
    int A, B, C;
    cin >> A >> B >> C;
    memset(dp, 0, sizeof(dp));
    for (int a = 99; a >= A; --a) {
        for (int b = 99; b >= B; --b) {
            for (int c = 99; c >= C; --c) {
                dp[a][b][c] += (double)(a)/(a+b+c) * (dp[a+1][b][c] + 1);
                dp[a][b][c] += (double)(b)/(a+b+c) * (dp[a][b+1][c] + 1);
                dp[a][b][c] += (double)(c)/(a+b+c) * (dp[a][b][c+1] + 1);
            }
        }
    }
    cout << fixed << setprecision(10) << dp[A][B][C] << endl;
}

メモ化再帰による実装

今回は DP の更新順序がちょっとわかりにくい。こういうときはメモ化再帰をすると、何も考えずに実装できる！

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

double dp[110][110][110];
double rec(int a, int b, int c) {
    // 終端条件
    if (a >= 100 || b >= 100 || c >= 100) return 0.0;

    // メモ化
    if (dp[a][b][c] >= 0.0) return dp[a][b][c];
            
    double res = 0;
    res += (double)(a) / (a+b+c) * (rec(a+1, b, c) + 1);
    res += (double)(b) / (a+b+c) * (rec(a, b+1, c) + 1);
    res += (double)(c) / (a+b+c) * (rec(a, b, c+1) + 1);

    // メモ化しながらリターン
    return dp[a][b][c] = res;
}

int main() {
    int A, B, C;
    cin >> A >> B >> C;
    memset(dp, -1, sizeof(dp));
    cout << fixed << setprecision(10) << rec(A, B, C) << endl;
}

けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

AtCoder ABC 184 D - increment of coins (水色, 400 点)