AIで解説 AtCoder攻略　ヒープ・イベント掃引

ヒープ・イベント掃引ページの位置づけ

項目	内容
必修度	重要
学習目安	標準
前提	ソート・heapq
対象問題	18問（推定値あり18問、未算出0問）

この記事のdifficulty区分は、問題を解く順番を決めるための目安です。AtCoderの公式なA〜F区分ではなく、取得できたdifficulty推定値を次の範囲に分けています。

学習目安	difficulty推定値	問題数
入門	difficulty < 0	3
標準	0〜799	4
標準〜発展	800〜1199	3
発展	1200以上	8
未算出	—	0

時刻や値の順序を保ちながら、最小値や中央値を取り出します。古くなった要素を捨てる条件を明示します。

問題ごとの細かな実装は異なりますが、最初に確認する条件は共通しています。

ヒープ・イベント掃引の見分け方

追加と最小値取得が交互に起きる
時刻順に区間が有効になる
中央値や最小候補をオンラインで求める

ヒープ・イベント掃引の実装前チェック

ヒープに入れるキーを決める
期限切れ要素を取り除く
Pythonの最小ヒープを反転して使う方法を確認する

先に確認する文法・ライブラリ

まずは必須Python文法で、入力・配列・条件分岐・ループなどの基本を確認してください。問題に合わせたキュー、ヒープ、二分探索などの選び方は標準ライブラリ・定石にまとめています。

代表問題で実装を確認する

最初の一問として、ABC141 D Powerful Discount Tickets（公式解説）を解きます。半額にするたびに最も高い商品を選ぶのが得です。heapqは最小ヒープなので、価格にマイナスを付けて最大ヒープとして使います。

import heapq

N, M = map(int, input().split())
A = list(map(int, input().split()))
heap = [-value for value in A]
heapq.heapify(heap)

for _ in range(M):
    price = -heapq.heappop(heap)
    heapq.heappush(heap, -(price // 2))

print(-sum(heap))

毎回最大値を探すとO(MN)ですが、ヒープなら1回O(log N)、全体O((N+M)log N)です。

ヒープ・イベント掃引の学ぶ順番

このページでは全件を一度に並べず、difficultyの推定値を目安に代表問題を段階分けしています。難易度が未算出の問題は、制約と出題意図を先に確認します。

まず解く

問題	公式解説	出題意図	difficulty
ABC414 A Streamer Takahashi	公式解説	公式Editorialの方針を streamer window count として整理する。	-1044
ABC446 B Greedy Draft	公式解説	Use a priority queue to implement the greedy draft order.	-366
ABC294 C Merge Sequences	公式解説	2つの列を統合した順位をソートと二ポインタで求める。	-59
ABC329 D G. Election Quick Report	公式解説	After each vote, update the current leader with a heap.	232
ABC294 D G. Bank	公式解説	未対応の最小番号と呼び出し済み集合を管理し、各窓口操作を処理する。	385

次に解く

問題	公式解説	出題意図	difficulty
ABC243 C Collision 2	公式解説	同じ高さの人を位置順に並べ、Rの後にLが現れる組があるかで衝突を判定する。	409
ABC234 D G. Prefix K-th Max	公式解説	先頭からの各区間を最小ヒープで管理し、K個を超えたら最小を捨ててK番目最大を出力する。	503
ABC141 D Powerful Discount Tickets	公式解説	割引券を1枚ずつ最も高い商品に適用する貪欲法を、最大ヒープでO(M log N)に実装する。	823
ABC323 D G. Merge Slimes	公式解説	Repeatedly merge the two smallest slimes and insert their sum.	852
ABC320 E H. Somen Nagashi	公式解説	Process arrival times with a min-heap and distribute noodles to waiting customers.	1096

挑戦問題

問題	公式解説	出題意図	difficulty
ABC306 E H. Best Performances	公式解説	Maintain the top K performances with two multisets and their running sum.	1268
ABC308 F I. Vouchers	公式解説	Sort products by price and greedily apply the largest eligible voucher discount with a heap.	1284
ABC281 E H. Least Elements	公式解説	Maintain K smallest values in a window with two multisets and update their sum as the window slides.	1334
ABC325 D G. Printing Machine	公式解説	Sort jobs by start time and process available jobs in deadline order.	1367
ABC170 E Smart Infants	公式解説	Maintain each kindergarten’s ordered ratings and a global ordered multiset of kindergarten maxima; update the two affected groups for every transfer and output the global minimum maximum.	1502