競プロ典型90問の001 Yokan Partyで決め打ち二分探索をするときに、なぜ貪欲法で良いのかを証明する
この問題について研究室の先輩と話してたら疑問が沸き起こったので、先輩と共にきっちりと証明してみたappbird.icon
以下を証明する。
スコア$ Wを決め打つ。
この時次が成立する。
貪欲法によってようかんを切ったとき、すべてのようかんの各切れ端が$ W以上の長さになるよう切れる
<====> すべてのようかんの各切れ端が$ W以上の長さになるよう切れる
===> 方向
これは明らかである。
貪欲法でようかんの各切れ端が$ W以上の長さになるよう切れた時、
それは$ W以上の切れ端の長さで切れたことを意味する。
したがって、示せた
<==== 方向
対偶をとって、次を示す。
貪欲法によってようかんを切ったとき、ようかんの切れ端が$ W未満になるようなものが存在する。
===> すべてのようかんの切れ端が$ W以上の長さになるように切ることはできない。
すべてのようかんの切れ端が$ W以上の長さになるように切れたと仮定する。
今回の戦略は、$ \{A_1, \cdots, A_n\}の部分集合として表せる。（切った場所を含むような集合）
「貪欲法によってようかんを切ったとき、ようかんの切れ端が$ W未満になるようなものが存在する」とは、
次のような切り方$ \{A'_1, \cdots, A'_K\}として表す。が存在することである。
左端にだけ、長さ$ W未満の羊羹の切れ端$ (A'_i, A'_j)が存在する
それ以外の切れ端は全て長さ$ W以上であり、前の切れ端から初めて$ W以上開いた位置に切り口が存在する。
（貪欲法の挙動による）
https://scrapbox.io/files/67061f90c8785b001cae333f.png
以降、切れ口$ A_1, \cdots, A_nが左から順に並んでいることを想定する。
仮定から、すべてのようかんの切れ端が$ W以上の長さになるように切れているはずなので、
そのような切れ口$ \{B'_1, \cdots, B'_K\}がどこにあるのかを考えていく。
1. すべての切れ口は貪欲法のそれから左に動かすことはできない
はじめに、$ B'_1は$ A'_1よりもようかん上で左に存在しない。
厳密には、$ B_1' = A_i, A'_1 = A_jとしたとき、$ i \geq jとなる。
なぜなら、左端と$ B_1'からなる切れ端が$ W以上にならないためである。
続けて、$ B'_2は$ A_2'よりも左に存在しない。
なぜなら、$ B'_1は少なくとも$ A_1'の位置かそれよりも右にある。
$ A_2'と同じもしくはより右になければ、$ B'_1, B_2からなる切れ端が$ W以上にならないため。
同様に$ B'_{k}が$ A_{k}よりも左に存在しなければ、$ B'_{k+1}は$ A_{k+1}よりも左に存在しない。（$ k \leq K -1）
したがって、$ B'_{K}も$ A'_{K}より左に存在することはない。
2. しかし、仮定から最後の$ B'_Kは$ A'_Kより左に存在しなくてはならない。
左端と$ B_K'のなす長さは$ W以上でなくてはならないが、左端と$ A'_Kのなす切れ端の長さは$ Wに足りていない。
$ B_K'の位置に関して矛盾したため、すべてのようかんの切れ端は$ W以上の長さになるように切れない。