【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 --- 同期キュークラス
ソースコード:Lib/queue.pyqueueモジュールは、複数プロデューサ-複数コンシューマ(multi-producer,multi-consumer)キューを実装します。これは、複数のスレッドの間で情報を安全に交換しなければならないときのマルチスレッドプログラミングで特に有益です。このモジュールのQueueクラ...
collections --- コンテナデータ型
ソースコード:Lib/collections/__init__.pyこのモジュールは、汎用のPython組み込みコンテナdict,list,set,およびtupleに代わる、特殊なコンテナデータ型を実装しています。,,namedtuple(),名前付きフィールドを持つタプルのサブクラスを作成するファクトリ関数,,deq...

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
AtCoderisaprogrammingcontestsiteforanyonefrombeginnerstoexperts.Weholdweeklyprogrammingcontestsonline.

空の数列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
AtCoderisaprogrammingcontestsiteforanyonefrombeginnerstoexperts.Weholdweeklyprogrammingcontestsonline.

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

反転と要素を先頭か末尾に追加する操作があるので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をコピーしました