perogram

二分探索と凸関数とマンハッタン距離

Quiz

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より手前に答えがある