ABC 137 pythonのプライオリティキューを使おう

どうもーーー

近頃はアプリ開発したり、ハッカソン参加したりしてます。

昨日はABC137に参加したのですが惨敗してしまいました。

A,B,Cの3完で、Cで9ペナを出して90分ぐらいになりました（泣）
めちゃくちゃ悔やまれますが、気を取り直してやっていきたいと思います。

以下レーティング推移

伸び悩み。

さて、D問題は解けなかったのですが、考え方は合ってて、Priority Queueを使っていれば通せてました。
完全に頭の中から抜けていた。。。

過去にも何回かPriority Queueの問題に出くわしたことはあったのですが、なんか面倒で勉強せず放置しておきました。

今後はそのような惨事を防ぐため、ここで復習しておきたいと思います。

とりあえずDの解答から（メイン部分のみ）

N, M = LI()
AB = [LI() for _ in range(N)]
# 日付ごとに報酬をまとめる
AB_dict = {}
for ab in AB:
    if ab[0] not in AB_dict.keys():
        AB_dict[ab[0]] = [ab[1]]
    else:
        AB_dict[ab[0]].append(ab[1])

ans = 0
pq = queue.PriorityQueue()
keys = AB_dict.keys()
for i in range(1, M+1):
    # 残りi日
    if i in keys:
        for ab in AB_dict[i]:
            # 最大値から取り出したいので以下のように入れていく
            pq.put((-ab, ab))
    if pq.empty():
        continue
    ans += pq.get()[1]
print(ans)

1日目からM日後までに稼げる報酬の最大値を求める問題です。
普通は1日目に何を選ぶかを考えるのですが、そうすると、最適な報酬が選べません。
例えば、報酬の高いものから選ぶようにすると、
3 10
2 1
1 15
のときに、
初日に15の報酬がもらえる仕事から選んでしまい、最適な戦略から外れてしまいます。

そこで逆の発想です（これはD問題とかに多いのでサクッと思いつきました）
M日目にする仕事は、1日後に報酬がもらえる仕事で報酬が最大のものを選ぶのが絶対最適です。
そうすると、M-1日目には、2日後、1日後に報酬がもらえる仕事の中で、
M日目に選ばなかった仕事のなかで報酬が最大の仕事を選ぶのが最適です。

このように考えると、必然的に1日目に選ぶ仕事が決められます。

これを実行するために、まずは報酬発生日時で仕事を分けていきます。

それを今回はdictに入れましたが、これはリストでも良いと思います。
その後、1日前、2日前、・・・とM日前までシミュレーションしていきます。

その際、dictから1日前の仕事の報酬をPriority Queueに入れていきます。
報酬最大の仕事を取り出したいので、(-(入れたい値), 入れたい値)という値をqueueに入れていきます。
priority queueは、要素を昇順にソートし、最小値から取り出すことができます。
ですので、-(入れたい値)を格納することで、最大の値が最初に出てくるようになります。

今回は、普通にforループを回してqueueに入れていきました。

あとはそれを取り出して解答に反映していくだけです。

このやり方でいつも使えるかはわかりませんが、一旦基礎的な使い方はこれで良いと思います。

以上