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

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

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

最初、「期待値の線形性」を使うのかなと思って迷走した... 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)

となる。「+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;
}