ABC376Eを解いた【優先度付きキュー】

筆者はレート700前後の茶色コーダ

ABC376当日にACできなかったE問題を解いていく

実装コード

A,B各要素をタプルにしておき、Aの昇順でソートする

このとき、Aの最大値は最低でもK番目以上が確定なので
そこから全探索すればいいようだ、

Bの総和の最小値は優先度付きキューで最大値を取りせるようにして現在のBと入れ替えればOK

main.py

import sys
import heapq
def rI(): return int(sys.stdin.readline().rstrip())
def rLI(): return list(map(int,sys.stdin.readline().rstrip().split()))
def rI1(): return (int(sys.stdin.readline().rstrip())-1)
def rLI1(): return list(map(lambda a:int(a)-1,sys.stdin.readline().rstrip().split()))
def rS(): return sys.stdin.readline().rstrip()
def rLS(): return list(sys.stdin.readline().rstrip().split())
def err(*args): print(*args, file=sys.stderr)

class Maxheapq:
    def __init__(self):
        self.q = []
    def push(self, v):
        heapq.heappush(self.q, -v)
        return v
    def pop(self):
        return -heapq.heappop(self.q)
    def get(self):
        return self.q[0] * -1
    def values(self):
        for _q in self.q:
            yield -_q

def main():
    T = rI()
    
    for _ in range(T):
        N, K = rLI()
        A = rLI()
        B = rLI()
        L = []
        q = Maxheapq()
        for a,b in zip(A,B):
            L.append((a,b))
        L.sort()
        s = sum(b for _,b in L[:K-1] if q.push(b))
        ans = float('inf')
        # err(N,K,L)
        # err(s,L[:K-1])
        for i in range(K-1,N):
            a,b = L[i]
            # err(a,b,s+b,a*(s+b))
            # err(list(q.values()))
            ans = min(ans,a*(s+b))
            q.push(b)
            s += b
            s -= q.pop()
        print(ans)
        
if __name__ == '__main__':
    main()

まとめ

ABC376Eを解いた
Aの最大値はソート
Bの総和は優先度付きキューで管理して解いた

振り返りでも触れたが、
当日はAではなくBの昇順でソートしていた

最大値を確定させるという視点ではAのソートしたほうが確かに有効

そこから残りを全探索すればいいという発想と
総和の計算で優先度付きキューを使うという発想が難しかった

自分の地力だとE問題やはり一捻り二捻り考える必要があると改めて認識