こここブログ

機械学習, 統計分析, 競技プログラミング, CTF, VR, ……テクノロジーへの憧憬に身を焼かれている人のメモ帳です

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

2019-08-13 公開

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

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

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

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

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

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

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

とのこと。

ポイントとして

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

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

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

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

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

juppy.hatenablog.com

貪欲法

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

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

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

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

といった感じみたい。

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


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

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

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

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

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