解説めちゃ頭いい なんか怪しいことしたら通った
概要
考察
最大値の最小化は二分探索！(素振り)最大値の最小化は二分探索！(素振り)最大値の最小化は二分探索！(素振り)
というわけで二分探索をする。よって解くべき問題は「全てのペアの醜さを$X$以下にできるか？」
ここで、以下の補題を示す。
整数$A<B<C<D$において、$A$と$C$,$B$と$D$を結ぶようなペアはほどくことができる
- その1. $0 \leq A+C \leq X$かつ$0 \leq B+C \leq X$のとき
$A+C<A+D<B+D$, $A+C<B+C<B+D$なので両方とも$0$以上$X$以下である。OK
- その2 $M \leq A+C \leq M+X$かつ$M \leq B+C \leq M+X$
その1と同様。
- その3 $0 \leq A+C \leq X$かつ$M \leq B+C \leq M+X$
正直ここが一番あやしい
$A+B<A+C$で、$0 \leq A+B$なので$A+B$に関しては条件を満たす。 2式を足すと$M \leq A+B+C+D \leq M+2X$という式が出てくるが、ここから$0 \leq A+B \leq X$を引いて$M \leq C+D \leq M+X$が残る よって$C+D$もOK
もう一つ補題を示す。
整数$A<B<C<D$について、$0 \leq A+B \leq X$かつ$0 \leq C+D \leq X$ならば$0 \leq A+D \leq X$かつ$0 \leq B+C \leq X$が成り立つ。
証明: $A+B<A+D<C+D$ $A+B<B+C<C+D$ おわり
また、$0$を$M$に、$X$を$M+X$に変えても同様の証明が適用できる。
これらを証明して、$0 \leq x+y \leq X$なるペア(これを以降タイプA) と$M \leq x+y \leq M+X$なるペア(これを以降タイプB) の境界は1つだけで、また全てのペアは交差しないことがいえる。
そこで、どこまでペアAとペアBに組み込めるかそれぞれ決定する。
ペアA内での最大の和(modをとらない醜さ)が$X$を超えない範囲を調べればよく、またペアの和は増加するので二分探索が適用できる。
ペアBでは最小の和を考え、それが$M$を超える範囲を調べればよい。最小値も増加するので二分探索が適用できる。また最大の和もまた増加するので、最小の和が$M$を超えた地点より右にずらすことはない。
Aの限界とBの限界が交差していれば$X$は達成可能で、そうでなければ不可能。
もう一つ、最も左の要素をペアBに組み込む場合がある。このときはそのまま計算し、二分探索で得られた答えとのminをとればよい。
提出
感想
二分探索3回でけっこうびっくりした。単調性には気を付けよう！
