【AtCoder】Pythonでキューを使う

はじめに

Pythonで使えるキューを理解して、AtCoderの問題で使いこなせるように解説していきます。

実際にAtCoderの問題でキューを使ったサンプルコードも紹介します。

キューとは

そもそもキューとは、レジに並んだ行列のように、先に入れたものが先に使われるデータ構造です。先に入れたものを先に使うことをFIFO(First In First Out)と呼びます。

一方で、スタックは最後に入れたものを先に使うデータ構造です。こちらはLIFO(Last In First Out)と呼びます。

Pythonのキュー

Pythonでキューを扱う場合には、以下の2つがあげられます。

  • queue.Queue
  • collections.deque

queue.Queueは一般的なキューです。

collections.dequeは、スタックとキューを一般化したもので、両端キュー(double-ended queue)と呼ばれます。両端キューなので、どちらの側へのappendpopO(1)で実行できます。

複数のスレッドで使うような場合はqueue.Queueを利用するのがいいみたいですが、AtCoderで使う場合はcollections.dequeでいいと思います。

queue --- 同期キュークラス — Python 3.9.4 ドキュメント
collections --- コンテナデータ型 — Python 3.9.4 ドキュメント

collections.deque

collections.dequeの使い方について紹介します。

キューの作成

dequeでキューを作成します。

from collections import deque

d = deque()

listからキューへの変換もできます。

from collections import deque

li = [1, 2, 3, 4]
d = deque(li)

追加

appendappendleftで両端への要素の追加をします。

O(1)で実行できます。

>>> from collections import deque
>>> d = deque([1, 2])
>>> d.append(3)
>>> d.appendleft(4)
>>> d
deque([4, 1, 2, 3])

取り出し

poppopleftで両端から要素を取り出します。

O(1)で実行できます。

>>> from collections import deque
>>> d = deque([1, 2, 3, 4])
>>> d.pop()
4
>>> d.popleft()
1

反転

reverseで反転できます。

>>> from collections import deque
>>> d = deque([1, 2, 3, 4])
>>> d.reverse()
>>> d
deque([4, 3, 2, 1])

AtCoderのサンプル問題

ABC066 C問題

C - pushpush
AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.

空の数列bに対して、別の数列aの要素を末尾に追加と反転する操作を繰り返してできる数列bを求める問題です。

要素を末尾と先頭で交互に追加していき、最後に要素数で反転するかどうか判定しています。

from collections import deque

n = int(input())
A = list(map(int, input().split()))

b = deque()
for i in range(n):
    if i % 2 == 0:
        b.append(A[i])
    else:
        b.appendleft(A[i])

if n % 2 == 1:
    b.reverse()

print(*b)

ABC158 D問題

D - String Formation
AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.

与えられたクエリに従って文字列を作成していく問題です。

反転と要素を先頭か末尾に追加する操作があるのでdequeを活用します。反転は毎回操作するとTLEになってしまうので、反転しているかどうかをbool型でもっておきます。

from collections import deque

s = input()
q = int(input())
query = []
for _ in range(q):
    query.append(list(input().split()))

que = deque(s)
reverse_flag = False
for i in range(q):
    if query[i][0] == '1':
        reverse_flag = not reverse_flag
    else:
        if query[i][1] == '1' and reverse_flag:
            que.append(query[i][2])
        elif query[i][1] == '1':
            que.appendleft(query[i][2])
        elif query[i][1] == '2' and reverse_flag:
            que.appendleft(query[i][2])
        else:
            que.append(query[i][2])

if reverse_flag:
    que.reverse()

print(''.join(que))

参考

タイトルとURLをコピーしました