AtCoder Beginner Contest 230 D 問題 Destroyer Takahashi

問題

提出解答

問題の概要

2つの整数 $a,b$ に対して, $[a,b]$ で, $a$ 以上 $b$ 以下の整数全体の集合とする. また, $[\![M]\!]$ で $M$ 以下の正の整数の全体の集合とする. 以下を満たす $I \subset [\![10^9-D+1]\!]$ のうち, 濃度の最小値を求めよ.

任意の $i=1,2, \dots, N$ に対して, $[x, x+D-1] \cap [L_i, R_i] \neq \emptyset$ である $x \in I$ が存在する.

制約

$1 \leq N \leq 2 \times 10^5$
$1 \leq D \leq 10^9$
$1 \leq L_i \leq R_i \leq 10^9$

解法

次のようなアルゴリズムで正解できる.

必要ならば, $(L_1, R_1), \dots, (L_N, R_N)$ を並び替えて, $R_1 \leq \dots \leq R_N$ とする.
$X \gets -\infty, K \gets 0$ とする.
の順に以下を実行する.
- $X+D \leq L_i$ だった場合, $K$ に $1$ を加算して, $X \gets R_i$ とする.
$K$ を出力する.

このアルゴリズムの正当性のために, 以下を証明する.

条件を満たす $I \subset [\![N]\!]$ 全体の集合を $\mathcal{I}$ , その元のうち, 濃度の最小値を $\alpha$ とする. このとき, $I \in \mathcal{I}, |I|=\alpha$ であって, $\min I=\min R$ となるものが存在する.

(証明)
$I \in \mathcal{I}$ で, $|I|=\alpha$ を満たすものを取ってくる. ここで, $\min R=R_1$ としてもよい.

$\min I \gt R_1$ だった場合
$L_1 \leq R_1 \lt \min I$ なので, どのような $x \in I$ に対しても, $[x,x+D-1] \cap [L_1,R_1]=\emptyset$ となってしまい, $I \in \mathcal{I}$ であることに矛盾する.
だった場合
- $\min I \lt L_1$ だった場合
  $y=\min I$ とする. $[y, y+D-1] \cap [L_i, R_i] \neq \emptyset$ となる任意の $i$ に対して, $L_i \leq L_1 \leq R_1 \leq R_i$ より, $[L_1,R_1] \subset [L_i, R_i]$ なので, $I \setminus \{x\} \in \mathcal{I}$ となり, 最小性に矛盾する.
- $\min I \geq L_1$ だった場合
  $J:=(I \setminus \{\min I\}) \cup \{R_1\}$ とすると, これが所望のものである.