ABC463 D - 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}

布を右端が小さい順に並べると、次の順になる。

[2, 7], [5, 9], [1, 12], [9, 13], [10, 18], [15, 20]

スコア $x$ を達成できるかを二分探索する。
判定では、右端の小さい順に布を見ていく。
最初の $1$ 枚は選び、それ以降は直前に選んだ布との距離が $x$ 以上なら選ぶ。

二分探索中の判定は次のようになる。

$x$	貪欲に選ばれる布	選べる枚数	$3$ 枚選べるか
$9$	$[2,7]$	$1$	できない
$4$	$[2,7],[15,20]$	$2$	できない
$2$	$[2,7],[9,13],[15,20]$	$3$	できる
$3$	$[2,7],[10,18]$	$2$	できない

したがって、達成できる最大のスコアは $2$ となる。

特になし。

特になし。