最大化を二分探索で
$ \max_x f(x) を $ f(x) > X を満たす解の存在判定問題にしてXを二分探索する
xが順列や部分集合などで全探索不可能なサイズ
max f(x)を求める貪欲アルゴリズムが思いつかない時、f(x)>Xを満たす解の存在判定にすると、最大の解に限らず見つければ良いのでやりやすくなる
「答えを決め打つ」タイプの二分探索を使いこなそう - ARMERIA
最大化は二分探索
和の比率の最大化