ABC 320 E — Somen Nagashi

考察

列にいる人は常に元の番号順に並ぶため、そうめんを受け取るfrontは在列者の最小番号である。

列を離れた人は決まった時刻T_i+S_iに戻るので、各そうめん時刻より前にreturn eventを時刻順で反映すれば現在の列を復元できる。

return時刻がそうめん時刻と同じならその人は既に列にいる扱いなので、同時刻ではreturnを先に処理する必要がある。

採用する候補: 在列者を番号ordered set、離脱者をreturn時刻min-heapで管理し、そうめんeventを時刻順にsimulationする。

棄却する候補: 各そうめん時刻に全N人を番号順に走査して在列者を探す。

N,Mとも2×10^5で、先頭付近が長く不在だと二次走査になる。

棄却する候補: 一度受け取った人をqueue末尾へ戻す。

復帰位置は受取順の末尾ではなく元の番号順であり、return時刻も人ごとに異なる。

available setを{1..N}、return min-heapを空、answerを0で初期化する。各(T_i,W_i,S_i)の前にheap先頭のreturnTime≤T_iを全てpopしてpersonをavailableへ戻す。availableが非空なら最小personをeraseしanswerへW_iを加え、(T_i+S_i,person)をheapへpushする。最後に全answerを出力する。

典型の発動条件

event sweep

発動条件: 時刻付き到着・復帰と入力済みeventを順にsimulationするとき。

次の主event前にpriority queueから期限到来eventを処理する。

ordered setでの最優先対象

発動条件: active集合から最小IDを取り出し、後で再挿入するとき。

在列者のbeginをfront personとして使う。

問題固有の要素

列の物理的な詰め直しをsimulationせず、「在列中の番号集合の昇順」が列そのものを完全に表す。

別の問題へ持ち帰る視点: 順序が固定keyで復元できる待ち行列では、位置更新ではなくactive key集合として管理する。

正当性

そうめん時刻T_iはstrictly increasingなので、入力をそのまま主event順として使い、return heapからtime≤T_iをすべて移すだけでよい。 列が空ならeventは誰にも影響せず、新しいreturn eventも生成しない。 最小番号の取得・削除と時刻以下の復帰をどちらも対数時間で処理できる。

実装上の注意

  • returnTime==T_iも先に復帰させるためheap条件を<ではなく≤にする。
  • 獲得量累積とreturn時刻は32bitを超え得るので64bit整数を使う。

復習の核

  • 人の復帰とそうめんが同時刻の例、列が空の例、番号の大きい人が先に復帰する例を追ってevent順とset最小値を確認する。

計算量と制約

時間

O((N+M)log N)、Mそうめんevent、各受取は一returnを生成。

空間

O(N+M)、通常heapの同時entry数≤N。

制約との対応

公式制約の確認範囲: Time limit: 2 sec; Memory limit: 1024 MiB; Constraints: 1 \leq N \leq 2\times 10^5; 1 \leq M \leq 2\times 10^5; 0 <T_1 <\ldots < T_M \leq 10^9; 1 \leq S_i \leq 10^9; 1 \leq W_i \leq 10^9; All input values are integers.

出典

分類・前提・執筆情報

掲載状態: 収録済み

Somen Nagashi の公式問題ページ(外部リンク)

最終確認:

学習上の位置付け

主題の単元: event順にactive集合を更新する

主題
追加で学ぶ技能
    なし
    既習技能
    • priority queue・best-first列挙: 現在のfrontierの極値をheapで確定し、新しく解禁された候補だけを追加して上位K個や最良状態を列挙する。その発動条件、正当性、計算量を説明し、未知問へ実装できる。
    • ordered set・multisetの動的順序管理: 比較順を保つ集合でpredecessor/successor・極値・重複・二集合のk-smallest aggregateを更新する。その発動条件、正当性、計算量を説明し、未知問へ実装できる。

    主タグ: event・値順のオフライン走査

    補助タグ: ordered set・multisetの動的順序管理 priority queue・best-first列挙

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

    学習の位置

    体系上の位置: event順にactive集合を更新する

    • 値・時刻・座標順にeventを並べ、同値eventの処理順とactive集合の増分更新を設計できる。

    先に読む単元:

    • ordered set・multisetの動的順序管理 — 比較順を保つ集合でpredecessor/successor・極値・重複・二集合のk-smallest aggregateを更新する。その発動条件と正当化原理を比較可能な独立教材として学ぶ。
    • priority queue・best-first列挙 — 現在のfrontierの極値をheapで確定し、新しく解禁された候補だけを追加して上位K個や最良状態を列挙する。その発動条件と正当化原理を比較可能な独立教材として学ぶ。

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

    • 更新を単に逆順へ読む処理、答えの局所寄与だけを集計する順序交換、sort-uniqueしたkeyの添字化、および固定方向の単純scan。

    学習記録

    状況更新: 更新記録なし

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

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

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

    同じ単元の問題