Quiz
- https://yukicoder.me/problems/no/513
- インタラクティブ問題
- query(x, y)を投げると、宝までのマンハッタン距離が返ってくる
- 最大100クエリで場所を求めよ
ACコード
https://yukicoder.me/submissions/351288
x, yは独立に求められる
- 以下ではxを求める方法について述べる
凸関数は三分探索が定石
- しかしクエリ数をオーバーしてしまう
- 探索範囲を2/3にするために、2クエリを消費する
二分探索でいける
- 探索範囲をleft, rightとする
- leftでの距離を測る
- left_d = query(x=left, y=0)
- center = (left+right)/2とする
- マンハッタン距離なのでcenterでの距離も予測できる
- center_d = left_d - (leftとcenterの距離)
- centerより向こう側(right側)に答えがある場合、予測とクエリ結果が一致する
- 一致しなければcenterより手前に答えがある
