ABC184D increment of coins

問題

袋の中に金貨が枚、銀貨が枚、銅貨が枚入っています。この時、どれかの硬貨が100枚になるまで次の操作を続けます。

• 袋の中の硬貨をランダムに1枚取り出し、同じ種類の硬貨を2枚戻す。

この時、操作回数の期待値を求めなさい。

制約

考え方

期待値、ほい来た線形性！！...あれ？
はい、この問題貨幣一枚取り出すごとにその確率が前の各々の硬貨の枚数に依存するし終了時点での硬貨の総枚数が状態によって異なるので線形性使おうとすると破滅しますね、困ったな―
コンテスト中にほんとに困ったのでとりあえず「期待値　競プロ」あたりで検索してみます。

ひとまず検索は基本

んー、やっぱり線形性が基本ぽいしなんか問題をうまく読み替えればいいのかなー、うん？

D...P...？
制約から状態の種類はくらい...、そしてD問題...(その当てはめ方はどうなんだ)
はい、見えましたね、DPで解けそうなことがわかったらあとは遷移を考えるだけです。

解法1

私がコンテスト中に考えた解法です。金貨の数が枚、金貨の数が枚、金貨の数が枚となる確率をdp[a][b][c]とすると、遷移が配るDPでうまく書けそうです。すなわち、

dp[a+1][b][c] += dp[a][b][c]*(double)a/(a+b+c);
dp[a][b+1][c] += dp[a][b][c]*(double)b/(a+b+c);
dp[a][b][c+1] += dp[a][b][c]*(double)c/(a+b+c);

と書けますね、後は操作1回ごとに硬貨の総枚数が1枚ずつ増えることを考慮すると、のどれか一つのみがである状態のとdp[a][b][c]の積を各々足すことで期待値が求まります。

解法1コード

#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for (int i = 0;i < (int)(n);i++)
using ll = long long;


double dp[110][110][110];

int main()
{
  cout << fixed << setprecision(15);

  ll A,B,C; cin>>A>>B>>C;
  dp[A][B][C]=1.0;
  
  for(int a=A;a<=100;a++) for(int b=B;b<=100;b++) for(int c=C;c<=100;c++) {
    //a,b,cのいずれかが100ならその時点で遷移終了
    ll count=0;
    if(a==100) count++;
    if(b==100) count++;
    if(c==100) count++;
    if(count) continue;
    
    dp[a+1][b][c]+=dp[a][b][c]*double(a)/(a+b+c);
    dp[a][b+1][c]+=dp[a][b][c]*double(b)/(a+b+c);
    dp[a][b][c+1]+=dp[a][b][c]*double(c)/(a+b+c);
  }
  
  double ans=0;
  for(int a=A;a<=100;a++) for(int b=B;b<=100;b++) for(int c=C;c<=100;c++) {
    //a,b,cのいずれか1つのみが100の状態の確率だけ考える。
    ll count=0;
    if(a==100) count++;
    if(b==100) count++;
    if(c==100) count++;
    if(count!=1) continue;
    
    ans+=((a+b+c)-(A+B+C))*dp[a][b][c];  
  }
  
  cout<<ans<<'\n';
  return 0;
}

解法2

俗にいう期待値DPというやつですね。dp[a][b][c]を金貨が枚、銀貨が枚、銅貨が枚から始めたときの期待値と置くと、今度は貰うDPできれいに書けますね。すなわち

dp[a][b][c] += dp[a+1][b][c]*(double)a/(a+b+c);
dp[a][b][c] += dp[a][b+1][c](double)b/(a+b+c);
dp[a][b][c] += dp[a][b][c+1](double)c/(a+b+c);
dp[a][b][c] += 1.0;

うーん綺麗、しかもこの解法だと最後に合計する手間がないのでぱっと思いつけるのならこっちのほうが良さそうですね。思いつけるようになりたい...。
どの問題かは言わないでおきますが期待値DPはEducational DP Contestでも扱われていたので、うん、やっぱり典型として使いこなせるようになっておこう。

解法2コード

#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for (int i = 0;i < (int)(n);i++)
using ll = long long;

double dp[110][110][110];

int main()
{
  cout << fixed << setprecision(15);

  ll A,B,C; cin>>A>>B>>C;
  for(int a=99;a>=A;a--) for(int b=99;b>=B;b--) for(int c=99;c>=C;c--) {
    ll s=a+b+c;
    dp[a][b][c]+=dp[a+1][b][c]*(double)a/s;
    dp[a][b][c]+=dp[a][b+1][c]*(double)b/s;
    dp[a][b][c]+=dp[a][b][c+1]*(double)c/s;
    dp[a][b][c]+=1.0;
  }
  
  cout<<dp[A][B][C]<<'\n';
  
  return 0;
}

感想

最近期待値/確率DPがABCで出ていなかった(もしかしたら私が参加し始めた3月から考えると初？)ので頭から抜け落ちてて手間取りました。検索したらすぐに出てきたからよかったものの精進しないとですね...。読んでいただきありがとうございました。