優先度付きキューと貪欲法（AtCoder Beginner Contest 137 D問題復習）

2019-08-13 公開 / 2019-09-08 更新

方針は立ったものの実装ができず、悔しい想いをしたAtCoder Beginner Contest 137(ABC137)のD問題。

「優先度付きキュー(priority queue)」という便利なデータ構造について知ったのでメモ。

「貪欲法」という考え方の理解が深まったので、貪欲法についてもメモ。

AtCoder(ABC137)お疲れさまでした。
A～C解いたものの、Dがダメだった。
残り1日の際は支払いまで1日の中でmaxのもの、残り2日の際は支払いまで2日以下の中で未選択でmaxのもの、...という方針は合っていたが、実装ができず。悔しい…。
優先度付きキューを勉強しよう。https://t.co/RGgm1Lsdmg

— こここ (@kokokocococo555) August 10, 2019

優先度付きキュー(priority queue)

優先度付きキュー（priority queue）とは

「最小値(あるいは最大値)を取り出すこと」に特化した配列

（蟻本 python プライオリティキュー heapq 競技プログラミング - じゅっぴーダイアリー より）

とのこと。

ポイントとして

• Pythonではheapqというパッケージを使用する
• キューに値を入れる（heappushする）と、最小値が先頭に来る
• キューから値を取り出す（heappopする）と、最小値を取り出す
• 最大値を扱いたい場合、-1を掛けた値をキューに入れ、取り出す際にまた-1を掛けるとよい

最大値のみを保持・更新していく問題であればansをmax(ans, x)で更新していけば事足りる。

しかし今回のD問題では「何個になるか分からない値を最大値順に保持・更新する」必要があったため、優先度付きキューの使用が便利だった。

シンプルで使い勝手も良さそうなので、今後機会を見つけて使っていきたい。

---優先度付きキューの参考---

juppy.hatenablog.com

貪欲法

また、この問題の考え方は「貪欲法」というらしい（ABC137解説動画より）。

---D問題の解説---

名前は聞いたことがあったものの、よく分かっていなかった貪欲法。

「比較基準を統一した状態に落とし込んだ上で、1番良いものを選び続ける」

といった感じみたい。

実際に取り組んだ問題の中で知ると「こういうものなのか」とイメージしやすい。思わぬ収穫だった。

---

まずは緑色、できれば水色目指してがんばろう。

(2019-09-08 追記: 2019-09-07のABC140で緑色になりました！ -> Contest Result - AtCoder )

蟻本も読まないとなんだけど、なんだかとっつきにくく感じる。

プログラミングコンテストチャレンジブック [第2版]　?問題解決のアルゴリズム活用力とコーディングテクニックを鍛える?

他に良い本あったら教えてください。

---

<2019-09-08 追記>

同じような悩みがABC140の解説放送のコメント欄で議論されていた。

www.youtube.com

「螺旋本」というのが蟻本よりもとっつきやすいらしいので、読む。

プログラミングコンテスト攻略のためのアルゴリズムとデータ構造

---