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

hamayanhamayan's blog

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

~探索

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