ABC463D - Maximize the Gap

考え方

「あるスコア $x$ 以上が達成できるか？」は $x$ について単調である。
よって、この疑問の結果を $x$ で二分探索していけば、$O(\log (R_{\max}-L_{\min}))$ 回の判定で答えられる。

あとは、$1$ 回の判定をどうやるかだが、これはほぼ区間スケジューリング問題そのものである。
許される次のスタート位置を $x$ 離さなければならないことくらいしか違いがない。
よって、事前にソートをしておけば $1$ 回の判定は $O(N)$ で可能。

これで、全体として $O(N \log N + N \log (R_{\max}-L_{\min}))$ で解ける。

最後に、不可能な場合の答えを $-1$ に書き換えるのを忘れずに。
これは、二分探索の結果が $1$ 未満であるかどうかで判定できる。

入力を受け取る。

n: 6
k: 3
l: {1, 2, 5, 9, 10, 15}
r: {12, 7, 9, 13, 18, 20}

各布について、「右端、左端」の形にして、右端が小さい順に並べる。

vec: {(7,2), (9,5), (12,1), (13,9), (18,10), (20,15)}

スコア $x$ を達成できるかを二分探索する。
達成できる値の下限 inside を $0$、達成できない値の上限 outside を $20-2 = 18$ で初期化する。

inside: 0
outside: 18

まず、$x=9$ を達成できるか確認する。
右端が最も小さい布 (7,2) を選ぶ。
次に選ぶ布は、左端が $7+9=16$ 以上である必要がある。

vec: {(7,2), (9,5), (12,1), (13,9), (18,10), (20,15)}
x: 9
border: 16
counter: 1

左端が $16$ 以上である布は残っていないので、$1$ 枚しか選べない。
$k=3$ 枚以上選べないので、$x=9$ は達成できない。
outside を $9$ に更新する。

inside: 0
outside: 9

次に、$x=4$ を達成できるか確認する。
右端が最も小さい布 (7,2) を選ぶ。
次に選ぶ布は、左端が $7+4=11$ 以上である必要がある。

vec: {(7,2), (9,5), (12,1), (13,9), (18,10), (20,15)}
x: 4
border: 11
counter: 1

布 (20,15) を選べる。
これで $2$ 枚選べたが、$k=3$ 枚に足りていないので、$x=4$ は達成できない。
outside を $4$ に更新する。

inside: 0
outside: 4

次に、$x=2$ を達成できるか確認する。
右端が最も小さい布 (7,2) を選ぶ。
次に選ぶ布は、左端が $7+2=9$ 以上である必要がある。

vec: {(7,2), (9,5), (12,1), (13,9), (18,10), (20,15)}
x: 2
border: 9
counter: 1

布 (13,9) を選べる。
次に選ぶ布は、左端が $13+2=15$ 以上である必要がある。

border: 15
counter: 2

布 (20,15) を選べる。
これで $3$ 枚選べたので、$x=2$ は達成できる。
inside を $2$ に更新する。

border: 22
counter: 3
inside: 2
outside: 4

次に、$x=3$ を達成できるか確認する。
右端が最も小さい布 (7,2) を選ぶ。
次に選ぶ布は、左端が $7+3=10$ 以上である必要がある。

vec: {(7,2), (9,5), (12,1), (13,9), (18,10), (20,15)}
x: 3
border: 10
counter: 1

布 (18,10) を選べる。
次に選ぶ布は、左端が $18+3=21$ 以上である必要がある。

border: 21
counter: 2

左端が $21$ 以上である布は残っていないので、$2$ 枚しか選べない。
$k=3$ 枚以上選べないので、$x=3$ は達成できない。

inside: 2
outside: 3

inside と outside の差が $1$ になったので、二分探索を終了する。
達成できる最大のスコアは $2$ である。

よって、2 を出力する。

特になし。

特になし。