/ 
Time Limit: 0 msec / Memory Limit: 0 KiB
キーポイント
collections.dequeは両端キューのデータ構造。単なるキューを使いたい場合も、queue.Queueではなくこちらを使うことを推奨。collections.defaultdictはデフォルト値付き辞書。辞書にないキーにアクセスした場合、デフォルト値をセットして返す。collections.Counterは出現数をカウントするデータ構造。
collections とは
collections とは python の標準モジュールの 1 つです。
この節では、競技プログラミングにおいて比較的使う機会の多い deque, defaultdict, Counter の 3 つのクラスについて紹介します。
deque
deque は名前の通り deque (デック、両端キュー) というデータ構造を提供するクラスです1。列の両端への要素の追加、両端からの要素の取り出しを高速に行うことができます。
from collections import deque q = deque([1, 2, 3, 4, 5, 6]) # 左から順に 1, 2, 3, 4, 5, 6 の 6 個の要素が入った deque を生成 val1 = q.pop() # 右端の要素を取り出す。val1 は 6 val2 = q.pop() # val2 は 5 val3 = q.popleft() # 左端の要素を取り出す。val3 は 1 val4 = q.popleft() # val4 は 2 print(q) # 出力: deque([3, 4]) q.append(10) # 右端に要素を追加する。 q.appendleft(20) # 左端に要素を追加する。 print(q) # 出力: deque([20, 3, 4, 10]) print(len(q)) # 出力: 4 print(q[3]) # 出力: 10
pop, popleft, append, appendleft は定数時間で処理されますが、添字による deque 内の要素へのアクセスは線形時間かかることに注意してください。
| 操作 | 最悪計算量 |
|---|---|
| pop | O(1) |
| popleft | O(1) |
| append | O(1) |
| appendleft | O(1) |
| 添字によるアクセス | O(N) (N は要素数) |
以下のコードを、 AtCoder のコードテストで Python(CPython 3.13.7) を選択して実行した場合、case 1 の部分は 10ms 程度、case 2 の部分は 600ms 程度の処理時間がかかります。
from collections import deque
q = deque(range(200000)) # 200000 個の要素が入った deque を作成
# case 1
ans = 0
for _ in range(200000):
ans += q[0] # deque の先頭の要素を取得
print(ans)
# case 1 end
# case 2
ans = 0
for _ in range(200000):
ans += q[100000] # deque の真ん中の要素を取得
print(ans)
# case 2 end
なお、類似の機能を提供する queue.Queue というデータ構造もありますが、こちらは安全性重視の作りになっており2 collections.deque に比べ数倍程度遅いため、競技プログラミングにおいて使う機会はないでしょう。
練習問題
defaultdict
defaultdict は初期値付きの辞書(dict)です。
普通の dict では、存在しないキーにアクセスするとエラー (KeyError) が発生するため、存在しないかもしれないキーにアクセスするときは、get メソッドを用いることになります。
d = dict()
d.get("z", 100) # "z" が d のキーとして存在すればその値を、存在しなければ 100 を返す
# print(d["a"]) # Runtime error
print(d.get("a", 0)) # 出力: 0
# d["x"] += 10 # Runtime error
d["x"] = d.get("x", 0) + 10 # d["x"] は 10 になる
一方、defaultdict では辞書ごとに指定した初期値が自動でセットされます。
from collections import defaultdict d = defaultdict(int) # 0 を初期値とする print(d["a"]) # 出力: 0 d["x"] += 10 # d["x"] は 10 になる
defaultdict の引数に渡すものは「初期値にしたい値を返す関数」だと思うと良いでしょう3。例えば int() は 0 を返すため、defaultdict(int) は初期値が 0 となります。
自身で関数を定義すれば、初期値を自由に定めることができます。
from collections import defaultdict d1 = defaultdict(list) # 空のリストを初期値とする d1["a"].append(0) # d1["a"] は [0] になる d2 = defaultdict(lambda: 100) # 100 を初期値とする d2["x"] += 10 # d2["x"] は 110 になる
defaultdict への要素の追加、読み取りなどの各処理の計算量は、3.02節で説明した dict と同じです。
defaultdict は 便利な一方、意図しないキーにアクセスしたときにもエラーが出ないため、バグを見つけにくくなるデメリットがあります。通常の dict とどちらを使うのがよいか状況に応じて選択してください。
from collections import defaultdict
d1 = defaultdict(int)
N = 10
for i in range(N):
d1[i] = i
d2 = defaultdict(int)
for i in range(N): # range(N-1) を意図していたが誤って range(N) とした
d2[i] = d1[i+1] # d1[N] にアクセスしているがエラーにならない
また、読み出しただけでもそのキーが辞書に追加される点に注意してください。
from collections import defaultdict
d = defaultdict(int)
print(d[123]) # 出力: 0
print(d["x"]) # 出力: 0
print(len(d)) # 出力: 2
print(d) # 出力: defaultdict(<class 'int'>, {123: 0, 'x': 0})
Counter
Counter はその名の通り、数を数えるクラスです。リストなどを引数として渡すと、どの要素が何個あるかを辞書形式にしてくれます。
from collections import Counter
vals = [3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5]
c1 = Counter(vals)
print(c1) # 出力: Counter({5: 3, 3: 2, 1: 2, 4: 1, 9: 1, 2: 1, 6: 1})
print(c1[9]) # 出力: 1
print(c1[10]) # 出力: 0
c2 = Counter("abracadabra")
print(c2) # 出力: Counter({'a': 5, 'b': 2, 'r': 2, 'c': 1, 'd': 1})
print(c2["a"]) # 出力: 5
dict と同様に、 .keys(), .values(), .items() により、キー及び値についてイテレーションすることができます。
from collections import Counter
c = Counter([10, 10, 20, 30, 30, 30])
for key, value in c.items():
print(key, value)
実行結果
10 2 20 1 30 3
Counter 同士は加減算を行うことができます。キーが等しいもの同士で演算を行い、値が 0 以下となるものは削除されます。以下の最後の例で d に対応する値が -1 にはならならず、キーそのものが存在しないことに注意してください。
from collections import Counter
c1 = Counter("aaabbc")
c2 = Counter("abbbd")
print(c1) # 出力: Counter({'a': 3, 'b': 2, 'c': 1})
print(c2) # 出力: Counter({'b': 3, 'a': 1, 'd': 1})
print(c1 + c2) # 出力: Counter({'b': 5, 'a': 4, 'c': 1, 'd': 1})
print(c1 - c2) # 出力: Counter({'a': 2, 'c': 1})
Counter 内に存在しないキーにアクセスすると 0 が返されます。defaultdict とは異なりアクセス後もキーが増えることはありません。
from collections import Counter
c1 = Counter("aab")
print(c1) # 出力: Counter({'a': 2, 'b': 1})
print(len(c1)) # 出力: 2
print(c1["x"]) # 出力: 0
print(len(c1)) # 出力: 2
問題
本節にはEX問題はありません。本文中にある練習問題を解いてください。