AtCoder-ABC217 E - Sorting Queries【Python解答例】
AtCoder Beginner Contest217のE問題についてPythonの解答例を記事にしていきます。
AtCoder Beginner Contest 217 - AtCoder
AtCoder Beginner Contest217 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