【AtCoder】Pythonでキューを使う

2021.08.15

2024.03.24

競技プログラミング

AtCoderdequePythonキュー

はじめに

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)と呼ばれます。両端キューなので、どちらの側へのappendもpopもO(1)で実行できます。

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

queue --- 同期キュークラス

ソースコード: Lib/queue.py queue モジュールは、複数プロデューサ-複数コンシューマ(multi-producer, multi-consumer)キューを実装します。これは、複数のスレッドの間で情報を安全に交換しなければならないときのマルチスレッドプログラミングで特に有益です。このモジュールの Queue クラスは、必要なすべてのロックセマンティクスを実装しています。こ...

collections --- コンテナデータ型

ソースコード: Lib/collections/__init__.py このモジュールは、汎用の Python 組み込みコンテナ dict, list, set, および tuple に代わる、特殊なコンテナデータ型を実装しています。,, namedtuple(), 名前付きフィールドを持つタプルのサブクラスを作成するファクトリ関数,, deque, 両端における append や pop ...

collections.deque

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

キューの作成

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

1from collections import deque
2
3d = deque()

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

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

追加

appendとappendleftで両端への要素の追加をします。

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

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

取り出し

popとpopleftで両端から要素を取り出します。

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

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

反転

reverseで反転できます。

1>>> from collections import deque
2>>> d = deque([1, 2, 3, 4])
3>>> d.reverse()
4>>> d
5deque([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を求める問題です。

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

1from collections import deque
2
3n = int(input())
4A = list(map(int, input().split()))
5
6b = deque()
7for i in range(n):
8    if i % 2 == 0:
9        b.append(A[i])
10    else:
11        b.appendleft(A[i])
12
13if n % 2 == 1:
14    b.reverse()
15
16print(*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型でもっておきます。

1from collections import deque
2
3s = input()
4q = int(input())
5query = []
6for _ in range(q):
7    query.append(list(input().split()))
8
9que = deque(s)
10reverse_flag = False
11for i in range(q):
12    if query[i][0] == '1':
13        reverse_flag = not reverse_flag
14    else:
15        if query[i][1] == '1' and reverse_flag:
16            que.append(query[i][2])
17        elif query[i][1] == '1':
18            que.appendleft(query[i][2])
19        elif query[i][1] == '2' and reverse_flag:
20            que.appendleft(query[i][2])
21        else:
22            que.append(query[i][2])
23
24if reverse_flag:
25    que.reverse()
26
27print(''.join(que))