😎

浮動小数点型で比較して誤差で沼った話

2023/07/01に公開

コンテスト参加時のちょっとしたメモです。

問題

ABC 308 C-Standings

沼ったところ

この問題ではコイントスの成功率を比較する必要があります。
ここで問題文のままに浮動小数点型で比較すると、誤差が生じてしまい複数のテストケースでWAになります。

sort(ans.begin(), ans.end(), [](const pair<double, int64_t>& a, const pair<double, int64_t>& b) {
    if (a.first != b.first) return a.first > b.first;
    else return a.second < b.second;
});

誤差が考えられる問題で、強引に比較しようとしたため、なかなかテストケースを通すことができませんでした。

解決策

整数型で比較できるように、a[i]*(a[j] + b[j])a[j]*(a[i] + b[i])を比較します。
このように分母を払って変換することで整数型で比較できる様になります。

こちらに公式の解法があります。

得られた教訓

ここで重要だったのは、問題文を見たときに誤差を考える必要があることに瞬時に気づくことと、少数のテストケースでWAになったことを見て、バグの原因に当たりをつけることでした。

こちらの記事にバグ解消のTipsがまとめられています。

Discussion