ABC212_D,雑まとめ - 菊池律です。

問題文

高橋君は何も書かれていないたくさんのボールと1つの袋を持っています。最初、袋は空で、高橋君はQ回の操作を行います。それぞれの操作は以下の3種類のうちのいずれかです。

操作1: まだ何も書かれていないボール1つに整数(X_i)を書き込み、袋に入れる。
操作2: 袋に入っているすべてのボールについて、そこに書かれている数を、それに(X_i)を加えたものに書き換える。
操作3: 袋に入っているボールのうち書かれている数が最小のもの（複数ある場合はそのうちの1つ）を取り出し、そこに書かれている数を記録する。その後、そのボールを捨てる。

1≤i≤Q についてi回目の操作の種類(P_i)および操作1, 2における(X_i)の値が与えられるので、操作3において記録された数を順に出力してください。

制約

(1 <= Q <= 2 10⁵)
(1 <= P_i <= 3)
(1 <=X_i <= 10⁹)
入力は全て整数である。
(P_i = 3) であるようなiが1つ以上存在する。
(P_i = 3) であるとき、i回目の操作の直前の時点で、袋には1つ以上のボールが入っている。

入力

入力は以下の形式で標準入力から与えられる。

Q
P_1 X_1
P_2 X_2
:
P_Q X_Q

2行目からQ+1行目の各行は次のいずれかの形で与えられる。

1 X_i
2 X_i
3

まず、(1 \leq P_i \leq 3) が与えられる。これは操作の種類を表す。 (P_i = 1) または (P_i = 2) ならば、その後に空白区切りで (X_i) が与えられる。

出力

Q回の操作のうち操作の種類が(P_i = 3)であるような各操作について、記録された数を改行区切りで出力せよ。

普通にリストを使ってやろうとすると、操作2と3がネックになってしまう！

if q == 2:
    queue = [item + x_i for item in queue]
if q == 3:
    queue = min(queue)

1.操作2が来るたびリストの要素を全部呼び出してx_iを足していると、余裕でTLE。 2.また、pythonのリストのmin()関数は計算量にO(N)かかってTLEになる。まず思いついたのは、countを用意しといて、操作2が呼び出される時にcount += x_i をする。そして操作3が呼び出されたときにprint(数字+count)をする。

↓それで行こう！と思って提出したコード atcoder.jp

最小値を取り出さなきゃいけないのを忘れてWA！ dequeもリストもmin()関数はO(N)なので、かなり困ります。調べたら、優先度付きキューなるものがあるらしい。 qiita.com

操作1と操作3の時だけheapqを使う実装にすればいいので、実装自体は簡単！

import heapq
Q=int(input())
que=[]
cnt=0
for _ in range(Q):
    q=list(map(int,input().split()))
    if q[0]==1:
        heapq.heappush(que,q[1]-cnt)
    elif q[0]==2:
        cnt+=q[1]
    elif q[0]==3:
        print(heapq.heappop(que)+cnt)

実装の時のメモ書き

if q[0]==1:
        heapq.heappush(que,q[1]-cnt)

リストに要素を追加する時、x_iをそのまま追加しようとすると、それより以前に操作2が施されてた時に出力がおかしくなってしまわれる。例えば、

という入力の時、期待される出力は

4
5

だけど、 q[1]-cntをしないと、

5
6

が出力される。だから、操作1を施すタイミングでそこまでのcntを引いてあげて、操作3の時にcntを足してあげることで操作2でcntが更新されても問題なく出力される！

提出したコード

atcoder.jp