競プロ典型 90 問：048 - I will not drop out（★3）

問題

atcoder.jp

挑戦結果

• 挑戦日：2021/10/17
• 結果：解けた
• 時間：20分ぐらい

考えたこと

• 各秒で貪欲に点数が一番多い問題(部分点 or 満点狙い)に取り組むのが良い。それを上手に実装すればよさそう。
• 部分点は最初にソートしておいて、上から順に取り出していけばいいけど、満点狙いはそうもいかなそう。
• pythonだとheapq(優先度付きキュー)を使えば良さそう

公式解説

https://twitter.com/e869120/status/1396960059796582400/photo/1

解説を読んだふりかえり

• heapq使わなくても良さそうだった。あと、自分の実装のHQ1はheapqにする必要はまったくなかった。
• ソートして上からK個の合計で良かったのか。 から、満点狙いをする場合(の点数を取りに行く場合)には、対応する部分点は必ず取れていて、これに気がついていたら実装がすごく簡単になる。自分はこれに気がつけていなかった・・・。

ソース

import heapq
N, K = [int(x) for x in input().split()]
A,B = [],[]
HQ1,HQ2 = [],[]
for i in range(N):
    a,b = [int(x) for x in input().split()]
    A.append(a)
    B.append(b)
    # (部分点, 最高点までの差分)を優先度キューに入れる。(※最大化が欲しいので-にする)
    HQ1.append((-b,-(a-b)))

heapq.heapify(HQ1)

score = 0
for _ in range(K):
    # 部分点 or 最高点の大きい方を求める(-つける)
    s1 = -9999 if len(HQ1)==0 else -HQ1[0][0]
    s2 = -9999 if len(HQ2)==0 else -HQ2[0]
    # 部分点のほうが大きい場合
    if s1>s2:
        x,y = heapq.heappop(HQ1)
        score += (-x)
        # 満点用の優先度キューに追加
        heapq.heappush(HQ2,y)
    # 満点を狙ったほうがいい場合
    else:
        x = heapq.heappop(HQ2)
        score += (-x)

print(score)

解説読んだあと

import heapq
N, K = [int(x) for x in input().split()]
S = []

for i in range(N):
    a,b = [int(x) for x in input().split()]
    S.append(b)
    S.append(a-b)
S.sort(reverse=True)

print(sum(S[:K]))