ebisukeプログラミング初心者脱出黙示録

30歳を過ぎてから始めたプログラミングと競プロの記録。Pythonで取り組んでいます。Arduinoで電子工作も

AtCoder-ABC217 E - Sorting Queries【Python解答例】

AtCoder Beginner Contest217のE問題についてPythonの解答例を記事にしていきます。
AtCoder Beginner Contest 217 - AtCoder


AtCoder Beginner Contest217 E - Sorting Queries

E - Sorting Queries

問題文

空の列 A があります。クエリが Q 個与えられるので、与えられた順番に処理してください。
クエリは次の 3 種類のいずれかです。

・1 x : A の最後尾に x を追加する。
・2 : A の最初の要素を出力する。その後、その要素を削除する。このクエリが与えられるとき、A は空でないことが保証される。
・3 : A を昇順にソートする。

制約

・1≤Q≤2×10 ^5
・0≤x≤10 ^9
・クエリ 2 が与えられるとき、A は空でない。
・入力は全て整数である。

解答例

from collections import deque
import heapq

Q = int(input())

que = deque()
hq = []

for i in range(Q):
    query = input()
    if query[0] == "1":
        q, x = query.split(" ")
        que.append(int(x))
    elif query[0] == "2":
        if len(hq) > 0:
            print(heapq.heappop(hq))
        else:
            print(que.popleft())
    else:
        while que:
            heapq.heappush(hq, que.pop())

解説

公式解説を読んで解くことができました。

queと優先度付きキューを使って取り組みました。

クエリごとの方針は次の通りです。
・クエリ1:que.append(int(x))でqueの最後尾にxを追加する。
・クエリ2:優先度付きキューが空なら、que.popleft()でqueの最初の要素を出力する。
空でなければheapq.heappop(hq)で優先度付きキューから最小値を取り出し出力する。
・クエリ3:queが空になるまで、heapq.heappush(hq, que.pop())で優先度付きキューにqueの要素を追加する。

この操作を該当するクエリごとに実行することでACできました。

優先度付きキューでソートの計算量を削減することがポイントでした。




ABC217の関連記事はこちら
ebisuke33.hatenablog.com
ebisuke33.hatenablog.com
ebisuke33.hatenablog.com