コンテストでの時間切れや解けなかった過去問を振り返って供養していく

問題

Difficulty: 1370 (記事作成時点)

供養

解法

$( (a_{i}, 0), (b_{i}, 1) )$ について、$a_{i} \le A$ であるような線分のみ使用することを考える
- 簡単のため線分 $( (a_{i}, 0), (b_{i}, 1) )$ を $(a_{i}, b_{i})$ と表記する
$a_{j} \le A$ である線分のみでちょうど $k$ 個選択したときに、$k$ 個目の $b_{j}$ が最も小さくなるような選び方した場合の $k$ 個目の $b_{j}$ を $B_{A, k}$ とする
- このとき、存在する範囲において $B_{A, 1} \lt B_{A, 2} \lt \dots \lt B_{A, k}$ である
$(A, b_{i})$ を選び、かつ最も多く選ぶには、$a_{j} \lt A$ かつ $b_{j} \lt b_{i}$ であるような線分についての最も多い選び方をする必要がある
- すなわち、$B_{A - 1, k - 1} \lt b_{i}$ であるような最大の $k$ について、$k$ 個選ぶのが最大
- したがって、$B_{A, k} = \min (b_{i}, B_{A, k})$ となる
- $a_{i} = A$ であるような $(a_{i}, b_{i})$ を $b_{i}$ について降順に見ていけば、その時点において $B_{A, k - 1} \lt b_{i}$ であるような最大の $k$ について、$B_{A, k} = b_{i}$ に更新できる
  - 更新対象は二部探索で求められる
$(a_{i}, b_{i})$ を $a_{i}$ について昇順、同値の時は $b_{i}$ について降順に上記の方法で $B_{A, k}$ を更新していき、$B_{N, k}$ が存在する最大の $k$ が答
- 端的には、ソートした順に $b_{i}$ を並べた数列の LIS の長さ