誤差に気をつける問題では値が0の確認にEPSを使用せよ ～C. Need for Pink Slips～

問題

カードC, M, Pが確率c, m, pで配られる
それ以外のパラメータvがある
Pを引いたらゲームは終わり
C, Mを引いたら確率が変化する。ここではCを引いたとする
c<=vならc=0となり、c=invalidとなる。cの値は他のvalidな確率に分配される
c>vならc-=vとなり、減った分の確率vは他のvalidな確率に分配される
引く回数の期待値を求めよ

解説

  • 「c, mがどんどん減っていく」かつ「v>=0.1」なので、少ない回数で収束する
  • 再帰関数を書けばいい
  • 誤差に注意

誤差がどうWAになるか

  • 0と判定すべき時に誤差で0と判定できなかった場合、確率の分配の割り振り対象となってしまい、シミュレーションが狂う

誤差を切り抜ける方法

  • 整数を使う
  • equals, EPSを使う
using ld = long double;
constexpr ld EPS = 1e-14;
constexpr bool equals(ld a, ld b){return fabs((a)-(b)) < EPS;}

提出

code

ld f(ld c, ld m, ld p, ld v){
  ld exp=0;
 
  if(c>EPS){
    if(c<=v){
      // cは0になる
      if(m>EPS){
        // m is alive
        exp += c * (1+f(0,m+c/2,p+c/2,v));
      }else{
        // m==0
        exp += c * (1+f(0,0,1,v));
      }
    }
    else{
      // c>v
      if(m>EPS){
        // m is alive
        exp += c * (1+f(c-v,m+v/2,p+v/2,v));
      }else{
        // m==0
        exp += c * (1+f(c-v,0,p+v,v));
      }
    }
  }
 
  if(m>EPS){
    if(m<=v){
      // mは0になる
      if(c>EPS){
        // c is alive
        exp += m * (1+f(c+m/2,0,p+m/2,v));
      }else{
        // c==0
        exp += m * (1+f(0,0,1,v));
      }
    }
    else{
      // m>v
      if(c>EPS){
        // c is alive
        exp += m * (1+f(c+v/2,m-v,p+v/2,v));
      }else{
        // c==0
        exp += m * (1+f(0,m-v,p+v,v));
      }
    }
  }
  exp += p;
  return exp;
}
 
// for codeforces
void solve(){
  ld c,m,p,v;
  cin>>c>>m>>p>>v;
 
  ld ans = f(c,m,p,v);
  cout<<setprecision(20);
  p(ans);
}
 
int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
 
    // input
    ll N;
    cin>>N;
    
    while(N--)solve();
    
    return 0;
}