ABC471Dを解いた【優先度つきキュー】

筆者はレート800前後の茶～緑コーダ

ABC471のD問題を解いていく

実装コード

値から登録時刻を引いた値を優先度つきキューで管理し、取り出す時刻での最大値を求める。

• Q, V を受け取り、最大値を取り出すための Maxheapq を用意する
• クエリ1では、時刻 t に値 w を追加するとき、時刻による増加分を除いた w - t をキューに入れる
• w - t を保存しておくと、時刻 t での値は保存値に t を足すだけで求められる
• クエリ2でキューが空なら -1 を出力する
• キューに要素があれば最大の保存値 w0 を取り出し、現在の値 w0 + t を求める
• 現在の値と上限 V の小さい方を答えとして出力する

main.py

from bisect import bisect_left, bisect_right, insort_left, insort_right
from collections import defaultdict, Counter, deque
from functools import reduce, lru_cache
from itertools import product, accumulate, groupby, combinations
import sys
import os
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())
IS_LOCAL = int(os.getenv("ATCODER", "0"))==0
err = (lambda *args, **kwargs: print(*args, **kwargs, file=sys.stderr)) if IS_LOCAL else (lambda *args, **kwargs: None)

import heapq

class Maxheapq:
    def __init__(self):
        self.q = []

    def push(self, v):
        heapq.heappush(self.q, v * -1)

    def pop(self):
        return heapq.heappop(self.q) * -1

    def get(self):
        return self.q[0] * -1

    def values(self):
        for _q in self.q:
            yield -_q

def main():
    Q, V = rLI()
    que = Maxheapq()

    for _ in range(Q):
        q = rLI()

        if q[0] == 1:
            _, t, w = q
            que.push(w - t)
        else:
            _, t = q

            if not que.q:
                print(-1)
            else:
                w0 = que.pop()
                ans = min(w0 + t, V)
                print(ans)

if __name__ == '__main__':
    main()

感想

優先度つきキューを使うところまでは思いついたが、w - t を保存して時刻の影響を打ち消す発想は出なかった。
値が同じ速さで増えるときは、共通する時刻の部分を分けて考えると整理しやすいと感じた。