何で決め打ち二分探索は最小値を最大化する問題に有効なのか？
最小値を最大化する問題
何らかのスコアの列$ \{W_\lambda\}_\lambdaを定義します。
$ \min_{\lambda} W_\lambdaを最終スコア$ Wとしたときに
最終スコアを最大化したときの値を求めてください。
こういう問題の時、$ \min_\lambdaをどのように対処するかが難しい....appbird.icon
例
二分探索の下界・上界をそれぞれbegin, endとする。
以下を、begin == endとなるまで繰り返す。
1. 最終スコアの目標値$ w = \frac{begin + end}2を決め打つ
2. $ Wを$ w以上にできるかを判定する。
3. 二分探索の範囲更新
できれば、$ begin = wにして、もっと上の目標値が達成可能かどうかを調べる。
できなければ、$ end = wにして、もっと下の目標値が達成可能かどうかを調べる。
できないとわかった地点で、$ w以上の目標値については達成不可能だとわかる（単調性）appbird.icon なぜうまくいくか？
1. 二分探索の高速さ ... $ O(\log(end - begin))ステップで問題を解ける 「最小値を最大化する」という問題設定で「最大化する」という目標が定められているため単調性が確保されていることに起因する。 つまり、判定問題を判定するのに時間をかけやすくなる。
2. $ \minを含んだ式の評価からプログラムを書かずに、すでに定まった目標値に対して$ W_\lambdaを$ \lambdaごとに見ていく問題に帰着できる。
$ Wを$ w以上にできるかは、つまり$ \min_{\lambda \in \Lambda} W_\lambda \geq wであるかを判定することに相当する
もっと言えば全ての$ \lambdaに対して$ W_\lambda \geq wであるかを判定することになる
これは"最"小値の定義に起因する。
このようにすることで、$ \minをどう評価するかを考えず、$ wに対して$ W_\lambdaを$ \lambdaごとに見ていく問題に帰着できる。
「目標値"以上"にできるか」と噛み合うことによる
$ w分の自由度がなくなり固定されるため、問題が考えやすくなる
（高速に判定しやすくなる）
ここでこの判定問題が十分高速に判定することが難しければ、うまくいかない。