D - 高橋君ボール1号 (abc026_d)

Quiz

https://atcoder.jp/contests/abc026/tasks/abc026_d

Submit

https://atcoder.jp/contests/abc026/submissions/4013817

補足

• これは二分探索だな
• やってみると、単調増加ではないから二分探索が正常に動かない説
  • その後、ちゃんと動くと分かった
• テストケース2で、どうしても答えが合わない

[*] sample-2
[x] time: 0.019185 sec
[-] WA
output:
0.7806844588147

expected:
1.63372043395339

• なぜか？
  • 解が複数あるから
  • そうでした
• 提出したけれど精度の問題っぽく部分的にWA
• 他の人のコードを見て「long double」の存在を知った
• それを導入し、setprecision(15)として出力精度も上げたらAC

学び

• 単調増加・単調減少でなくても連続なら二分探索は動く
• long doubleなる型がある

プログラミングコンテスト攻略のためのアルゴリズムとデータ構造