NISHIO Hirokazu[Translate]
最大化を二分探索で
\max_x f(x) を f(x) > Xを満たす解の存在判定問題にしてXを二分探索する
xが順列や部分集合などで全探索不可能なサイズ
max f(x)を求める貪欲アルゴリズムが思いつかない時、f(x)>Xを満たす解の存在判定にすると、最大の解に限らず見つければ良いのでやりやすくなる



「答えを決め打つ」タイプの二分探索を使いこなそう - ARMERIA
最大化は二分探索

和の比率の最大化

Related Pages

  • →chokudai×貪欲法の証明パターン×選択肢が少ない方から貪欲×マトロイド×クラスカル法×区間スケジューリング×交換しても悪化しない×アルゴリズムとデータ構造×区間はマトロイドではない×abc076b×現在が良いほど未来も良い×poj3617×poj3069×ダイクストラ法×agc009a×arc111×abc187×arc110c×一回り小さい同じ形の問題×agc049b×abc103d×ABC023D×和の比率の最大化×単位時間ジョブスケジューリング問題×乱択＋貪欲×abc171_f×離散凸性→
  • 貪欲法
  • →最長増加部分列×dilworthの定理×座標圧縮×フェニック木×二分探索×更新され二分探索できる配列→
  • ABC134E
  • →二分探索×頻度表×ナップサック×条件付き最大値を対数オーダーで求める×最大クリーク×最大独立集合→
  • 半分全列挙
  • →二分探索×atcoder→
  • bisect
"Engineer's way of creating knowledge" the English version of my book is now available on [Engineer's way of creating knowledge]
(C)NISHIO Hirokazu / Converted from [Scrapbox] at [Edit]