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

hamayanhamayan's blog

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

~探索

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

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

  • Parallel Binary Search 解説(英語)
  • 複数の二分探索を1つに纏めるテクであるが、二分探索を纏めるというよりかは二分探索で同じような計算が沢山出てくるのでそれを1回に減らして二分探索していこうというモチベーション
  • 永続化で対応できる場合もあるらしい
  • 問題
  • AGC002 Stamp Rally 解説1 解説2
  • HR Selective Additions 解説