人工知能と競プロやってくブログ

深層学習・機械学習・AI・atcoder・競技プログラミングについて調べてやってみたことをまとめるブログです

AtCoder Beginner Contest 212 [ D - Querying Multiset ]をPythonで解く(400点、🟫茶diff)

問題

atcoder.jp

解法

最小値を計算量低く取り出すデータ管理構造、優先度付きキュー(priority queue)を使うことがポイント。
Pythonではheapqとして提供されている。

全体に対する玉の数の上下はoffset変数を作って管理。
玉を追加する時は、offset値を引いて追加する。

優先度付きキューの特徴

  • 最小値(最大値)を O(logN)O(log⁡N)で取り出す
  • 要素を O(logN)O(log⁡N) で挿入する
    ことが出来ます。 通常のリストだとそれぞれ O(N)O(N) ですので高速です。
    「リストの要素の挿入」と「最小値(最大値)を取り出す」ことを繰り返すような時に使います。

実装

参考

qiita.com