競プロチャレンジ供養会場: AtCoder Beginner Contest 214 E - Packing Under Range Regulations

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

問題

Difficulty: 1835 (記事作成時点)

供養

解法

• $x = 1, \dots , 10^{9}$ について、まだ箱に入れておらず $L_{i} \le x$ であるようなボールの集合を $B$ とする
• このとき、箱 $x$ に入れるべきボールは $B$ のうち $R_{i}$ が最小のもの
  • ここで選んだボールが $R_{i} \lt x$ の場合は条件を満たす入れ方は存在しない
• PriorityQueue を用いて以下の操作をする
  • $B$ が空の場合、箱に入っていないボールの $L_{i}$ のうち最小の $L_{i}$ まで $x$ をとばす
  • $L_{i} = x$ であるようなボールをすべて $B$ に追加する
  • まだ $B$ に含まれていないボールの $L_{i}$ のうち最小の $L_{i}$ について $x \lt L_{i}$ である間、以下の操作を実施する
    • $B$ に含まれるボールのうち、$R_{i}$ が最小のボールを選ぶ
    • 選んだボールを $k$ としたとき、$x \le R_{k}$ ならば $k$ を $B$ から除外する
      • 除外できないときは $x \ge R_{k}$ なので、条件を満たす入れ方は存在しない
    • $x$ を1増加させる
  • 最初に戻る
• 上記の操作を最後まで実施できれば Yes、そうでなければ No が答え

実装

計算量はテストケースごとに $O(N \log N)$

公式解説

躓いた点

• AVL木を使おうとして実装が間に合わなかった