2019-08-13 公開 / 2019-09-08 更新
方針は立ったものの実装ができず、悔しい想いをしたAtCoder Beginner Contest 137(ABC137)のD問題。
「優先度付きキュー(priority queue)」という便利なデータ構造について知ったのでメモ。
「貪欲法」という考え方の理解が深まったので、貪欲法についてもメモ。
AtCoder(ABC137)お疲れさまでした。
— こここ (@kokokocococo555) August 10, 2019
A~C解いたものの、Dがダメだった。
残り1日の際は支払いまで1日の中でmaxのもの、残り2日の際は支払いまで2日以下の中で未選択でmaxのもの、...という方針は合っていたが、実装ができず。悔しい…。
優先度付きキューを勉強しよう。https://t.co/RGgm1Lsdmg
優先度付きキュー(priority queue)
優先度付きキュー(priority queue)とは
「最小値(あるいは最大値)を取り出すこと」に特化した配列
とのこと。
ポイントとして
- Pythonでは
heapq
というパッケージを使用する - キューに値を入れる(
heappush
する)と、最小値が先頭に来る - キューから値を取り出す(
heappop
する)と、最小値を取り出す - 最大値を扱いたい場合、-1を掛けた値をキューに入れ、取り出す際にまた-1を掛けるとよい
最大値のみを保持・更新していく問題であればans
をmax(ans, x)
で更新していけば事足りる。
しかし今回のD問題では「何個になるか分からない値を最大値順に保持・更新する」必要があったため、優先度付きキューの使用が便利だった。
シンプルで使い勝手も良さそうなので、今後機会を見つけて使っていきたい。
---優先度付きキューの参考---
貪欲法
また、この問題の考え方は「貪欲法」というらしい(ABC137解説動画より)。
---D問題の解説---
名前は聞いたことがあったものの、よく分かっていなかった貪欲法。
「比較基準を統一した状態に落とし込んだ上で、1番良いものを選び続ける」
といった感じみたい。
実際に取り組んだ問題の中で知ると「こういうものなのか」とイメージしやすい。思わぬ収穫だった。
まずは緑色、できれば水色目指してがんばろう。
(2019-09-08 追記: 2019-09-07のABC140で緑色になりました! -> Contest Result - AtCoder )
蟻本も読まないとなんだけど、なんだかとっつきにくく感じる。
![プログラミングコンテストチャレンジブック [第2版] ?問題解決のアルゴリズム活用力とコーディングテクニックを鍛える? プログラミングコンテストチャレンジブック [第2版] ?問題解決のアルゴリズム活用力とコーディングテクニックを鍛える?](https://images-fe.ssl-images-amazon.com/images/I/41bHxtpurqL._SL160_.jpg)
プログラミングコンテストチャレンジブック [第2版] ?問題解決のアルゴリズム活用力とコーディングテクニックを鍛える?
- 作者: 秋葉拓哉,岩田陽一,北川宜稔
- 出版社/メーカー: マイナビ
- 発売日: 2012/01/28
- メディア: 単行本(ソフトカバー)
- 購入: 25人 クリック: 473回
- この商品を含むブログ (36件) を見る
他に良い本あったら教えてください。
<2019-09-08 追記>
同じような悩みがABC140の解説放送のコメント欄で議論されていた。
「螺旋本」というのが蟻本よりもとっつきやすいらしいので、読む。

プログラミングコンテスト攻略のためのアルゴリズムとデータ構造
- 作者: 渡部有隆
- 出版社/メーカー: マイナビ出版
- 発売日: 2015/01/30
- メディア: Kindle版
- この商品を含むブログを見る