はまやんはまやんはまやん

hamayanhamayan's blog

競技プログラミングにおける二分探索・三分探索問題まとめ

~探索

  • 二分探索は単調変化する関数に対して、YES/NOの境目を見つける探索 参考
  • 三分探索は凸関数である関数に対して、最大値・最小値を見つける探索 参考1 参考2
  • 二分探索・三分探索は気がつくまでが長い。単調性が無いかというのは常に考えておく
  • 「最大値の最小化」
  • リアクティブ問題と二分探索は相性がいい
  • 二分探索+全探索の高速化の話 ここ ここも

【発展的話題】並列二分探索