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