ABC 214 E — Packing Under Range Regulations

考察

各ボール i は整数番号 L_i 以上 R_i 以下の箱のどれか一つへ入り、異なるボールは異なる箱を使わなければならない。

箱番号を小さい順に見たとき、現在の箱へ入れられるボールのうち右端 R が最小のものは、将来使える箱が最も少ない。

棄却する候補: 区間に含まれる全ての箱を頂点として二部グラフを作り、完全マッチングの有無を調べる。

箱番号は 10 億まであり、区間内の各整数を頂点として生成できない。

採用する候補: 箱番号を昇順に走査し、左端を迎えた区間を優先度付きキューへ入れ、右端が最小の区間を現在の箱へ割り当てる。

締切が早いボールを先に使う交換法が成立し、明示する箱は実際に割り当てる位置だけでよい。

ある割当てが現在選んだ区間より右端の遅い区間を先に使っていても、両者を交換すれば可否を悪化させない。

候補キューが空なら、次の区間の左端までの箱にはどのボールも入れられないため、その位置へ直接ジャンプできる。

区間の左端を解禁時刻、右端を締切とみなし、疎な整数軸をイベント間で飛ばしながら最早締切優先で単位ジョブを配置する。

典型の発動条件

区間割当ての最早締切優先

発動条件: 各要素へ区間内の相異なる整数を一つずつ割り当て、実行時刻を選べるとき。

現在位置までに開始した区間から右端が最小のものを min-heap で選び、箱を一つ消費する。

疎な座標のイベント走査

発動条件: 座標範囲は巨大だが、状態が変化する入力端点と実際の処理回数だけは少ないとき。

候補が空の区間を一つずつ進まず、次に未処理の L_i へ現在位置を移す。

問題固有の要素

箱番号の上限は大きいが、一個のボールを置くたびに現在位置は一つだけ増え、空白区間は左端イベントへ飛ばせる。

別の問題へ持ち帰る視点: 巨大な整数軸でも、各座標で処理せず「次に候補が生じる座標」と「実際に資源を消費する回数」だけを追う。

正当性

貪欲で処理済みの箱まで一致する実現可能な割当てがある、と帰納する。現在箱番号をxとし、解禁済みのうち右端が最小のボールaを選ぶ。その実現可能解でaの箱をy≥xとする。xが空ならaをyからxへ移してよい。xに別のボールbがあるならa,bの箱を交換する。aにはL_a≤x≤y≤R_a、bにはL_b≤x≤yかつy≤R_a≤R_bが成り立つので、両方とも合法であり、以前に確定した箱は変わらない。従ってxで最早締切を選ぶ解を常に残せる。

もし最小右端R_a<xなら、未割当てのaに残る箱は全てx以上で、どこにも入れられない。この時点で実現可能解はない。候補が空なら、次の未解禁ボールの最小左端まで残るどのボールも置けず、その区間を飛ばしても可能性を失わない。全ボールを処理できたときは構成した割当て自体が実現可能解なので、判定は必要十分である。

実装上の注意

  • キューの最小右端が現在位置より小さくなった時点で、その区間には割り当て可能な箱が残っていないため直ちに不可能とする。
  • テストケースごとに区間列とキューを初期化し、キューが空のときだけ現在位置を次の左端へ進める。

復習の核

  • 区間から異なる整数を選ぶ問題では、左から場所を埋め、候補の中で将来の余裕が最小の右端を優先する。
  • 座標上限を見て配列化を諦めるだけでなく、候補集合が空の区間を安全に飛ばせる理由まで確認する。

計算量と制約

時間

O(N log N)、区間sortと締切heap。

空間

O(N)。

制約との対応

公式制約の確認範囲: Time limit: 3 sec; Memory limit: 1024 MiB; Constraints: 1 \le T \le 2 \times 10^5; 1 \le N \le 2 \times 10^5; 1 \le L_i \le R_i \le 10^9; The sum of N across the test cases in one input is at most 2 \times 10^5.

出典

分類・前提・執筆情報

掲載状態: 収録済み

Packing Under Range Regulations の公式問題ページ(外部リンク)

最終確認:

学習上の位置付け

主題の単元: 交換論から選択順を導く

主題
追加で学ぶ技能
    なし
    既習技能
    • priority queue・best-first列挙: 現在のfrontierの極値をheapで確定し、新しく解禁された候補だけを追加して上位K個や最良状態を列挙する。その発動条件、正当性、計算量を説明し、未知問へ実装できる。
    • event順にactive集合を更新する: 値・時刻・座標順にeventを並べ、同値eventの処理順とactive集合の増分更新を設計できる。

    主タグ: 貪欲法と交換論

    補助タグ: event・値順のオフライン走査 priority queue・best-first列挙

    執筆: abc-explanation-author1.1.1 / revision 2

    学習の位置

    体系上の位置: 交換論から選択順を導く

    • 局所選択の交換または候補の支配関係を示し、安全な順序・候補・caseを確定できる。

    先に読む単元:

    • event順にactive集合を更新する — 値・時刻・座標順にeventを並べ、同値eventの処理順を決めてactive集合を増分更新する。逆向き処理や寄与分解とは不変量が異なるため独立に学ぶ。
    • priority queue・best-first列挙 — 現在のfrontierの極値をheapで確定し、新しく解禁された候補だけを追加して上位K個や最良状態を列挙する。その発動条件と正当化原理を比較可能な独立教材として学ぶ。

    この解説で扱わないこと:

    • 対称操作による状態の正規化。

    学習記録

    状況更新: 更新記録なし

    復習設定更新: 更新記録なし

    端末内の保存状態を確認しています。

    要復習一覧 / 学習記録のバックアップ / 解説に戻る

    同じ単元の問題