MIS.W新歓コンテスト2020 Random Card Battle ～floatの精度は低い～

hackerrank

Quiz

f:id:peroon:20200424012818p:plain

https://www.hackerrank.com/contests/misw-welcomecontest2020/challenges/random-card-battle/problem

解法

  • A>BならX=0で勝てるので勝率100%
  • それ以外ならX=Aで全力で範囲を広げるのが最適

落とし穴（？）

  • 小数点以下、有効数字5桁、四捨五入で出力する形式だった
  • いつもはcoutしているが、printfの方が向いていると思い、それを使う
  • printfでは%fなどの変換指定子を使うが、long doubleは知らなかったのでfloatで進めたが、それが失敗だった
  • floatは4バイトで、精度は「その有効数字は約 7 桁」だそう。整数部分も合わせると精度が足りない
  • 精度が足りなくてWAというのは気づきづらいもので、コンテスト後にテストケースも確認して判明した
  • 改善策としては、いつもlong doubleを使い、変換指定子%Lfを使う

code 抜粋

using ld = long double;

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);

    // input
    ll N;cin>>N;

    VI A(N);
    VI B(N);

    rep(i,N)cin>>A[i];
    rep(i,N)cin>>B[i];

    ld sum=0;
    rep(i,N){
      ld a = A[i];
      ld b = B[i];

      // A is bigger, so use X=0
      if(A[i]>B[i]){
        sum += 1.0;
      }
      else if(A[i]==B[i]){
        sum += (ld)a / (2*a+1);
      }
      // A[i] < B[i]
      else if(2*A[i]<=B[i]){
        // if full-power, lose
        sum += 0;
      }
      else{
        // losing... but can win
        sum += (ld)(2*a - b) / (2*a+1);
      }
    }

    printf("%.5Lf\n", sum);
    return 0;
}

その他