👏

ABC 184 | D - increment of coins

2021/01/04に公開

競プロ

動的計画法

tech

問題

解法

金・銀・銅のどれかが100枚のときは操作回数の期待値は0である。
dp[i][j][k]を金i枚、銀j枚、銅k枚の操作回数の期待値とする。
$i, j, k$ の状態から1枚とるとどれかが1枚増えるので、取り出す確率にその後の操作回数をかけ取り出した1枚を足せば、 $dp[i][j][k]$ が求まる。
よって以下の式になる。

dp[i][j][k] = dp[i+1][j][k] \times \frac{i}{i+j+k} + dp[i][j+1][k] \times \frac{j}{i+j+k} + dp[i][j][k+1] \times \frac{k}{i+j+k} + 1

どれかが100枚のときは0ですでに求まっているのでそれぞれ99枚以下の状態で大きい方から順に求めればいい。

コード

実装時のTips

3次元をvectorでやるのは面倒なのでdoubleの配列とする。初期化を忘れないようにする。

#include <bits/stdc++.h>

#include <atcoder/all>

using namespace std;
using namespace atcoder;
using ll = long long;
using ld = long double;
using uint = unsigned int;
using ull = unsigned long long;
const int MOD = 1e9 + 7;

int main() {
  const int mx = 100;
  ll a, b, c;
  cin >> a >> b >> c;
  // dp[i][j][k]: 金貨i枚, 銀貨j枚, 銅貨k枚のときの操作回数の期待値
  double dp[mx + 1][mx + 1][mx + 1] = {};
  for (int i = mx - 1; i >= 0; i--) {
    for (int j = mx - 1; j >= 0; j--) {
      for (int k = mx - 1; k >= 0; k--) {
        if (i == 0 && j == 0 && k == 0) continue;
        ld v = 0;
        v += dp[i + 1][j][k] * i;
        v += dp[i][j + 1][k] * j;
        v += dp[i][j][k + 1] * k;
        v /= (i + j + k);
        v += 1;
        dp[i][j][k] = v;
      }
    }
  }

  cout << fixed << std::setprecision(12);
  cout << dp[a][b][c] << endl;
}

ABC 184 | D - increment of coins

問題

解法

コード

参考

Discussion