データ構造
競技プログラミングで使われるデータ構造の概要をまとめよう．基本的にPythonに関する内容です．
〇リスト
C言語での配列に相当
〇タプル
イメージは，イミュータブル（変更不可能）なリスト．タプルの要素を変更するとエラーになる．
code: python
a = (1, 2, 3, 4)
a1 = 5 # TypeError: 'tuple' object does not support item assignment setの要素や辞書のキーとしてリストを使うとエラーになる．代わりにタプルを使う
code: python
x, y = 1, 2
a = set()
# a.add(x, y) # TypeError: unhashable type: 'list' a.add((x, y)) # {(1, 2)}
〇集合 set （C++での std::set）
集合型．データの存在性を重視．O(1)でデータを含むか判定できる．データの追加／削除も$ O(1)
code: python
a = list(range(100))
print(50 in a) # O(|a|)必要
a = set(range(100))
print(50 in a) # O(1)で判定
順序がないので，個別の要素を指定して取り出すことができない．スライスも不可
code: python
a = set(range(100))
for x in a:
print(x) # どんな順序か分からないが，全ての要素をスキャンすることは可能
print(a2) # TypeError: 'set' object is not subscriptable 和集合（|），積集合（&），差集合（-）などの集合演算もある
部分集合の判定に<や>を使う．
code: python
A, B = {1, 2, 3}, {1, 2}
print(A > B) # A⊃Bの判定．⊇にしたいときは>=．もちろん，逆向きも可能
【参考】C++のstd::setだと，存在性判定／データの追加／削除に$ O(\log N)かかるが，指定値より小さい値の個数（二分探索）も$ O(\log N)で可能．
〇辞書 dict
イメージとしては，集合の値に相当するキーに対して，別の値が紐づくデータ構造．C++での連想記憶std::map
辞書にキーが登録済みか否かの判定がO(1)で実行可能
code: python
a = {'S': 5, 'A': 12, 'B': 32} # キー:値 のペア
for x in a: # ループで xに入るのはキー
print(x, ax) # S 5 (改行) A 12 (改行) B 32 print('C' in a) # O(1)で判定
キーが登録していない値を参照しようとするとエラーになる．
code: python
a = dict()
print(a) # {1: 100, 5: 200}
a2 += 1 # KeyError: 2 ← キーとして 2 が未登録 〇 defaultdict
初期値（デフォルト値）指定付きのdict（辞書）．KeyErrorを回避できる．
import する必要あり．
整数0で初期化する例．最もよく使うタイプ．
code: python
from collections import defaultdict
cnt = defaultdict(int) # 初期値をint型で行う．0で初期化される
print(cnt) # defaultdict(<class 'int'>, {}) <-- データなし
import random
for _ in range(3):
print(cnt) # defaultdict(<class 'int'>, {6: 1, 5: 1, 3: 1})
空リストで初期化する例
code:python
from collections import defaultdict
idx = defaultdict(list) # 初期値をlist型で行う．[]で初期化される
print(idx) # defaultdict(<class 'list'>, {}) <-- データなし
import random
for i in range(3):
print(idx) # defaultdict(<class 'list'>, {2: 0, 6: 1, 2}) 空集合で初期化するときは，defaultdict(set)
〇 スタック
キューと同じく，要素が動的に増減するデータを保管するときに用いる．
後入れ先出し．LIFO：Last In First Out．
Pythonではlistでも実装可能だが，dequeがよく使われる（処理が早い？）．importが必要
code: python
from collections import deque
stack = deque() # 空のスタック（＝キュー）を作成
for i in range(1, 5):
stack.append(i) # 1, 2, 3, 4 がスタックに追加
while stack: # while len(stack) > 0: と等価
print(stack.pop()) # スタックの最後から1つ要素を取り出す
# 出力結果： 4 (改行) 3 (改行) 2 (改行) 1 (改行)
〇 スタック／キュー
スタックと同じく，要素が動的に増減するデータを保管するときに用いる．
先入れ先出し．FIFO：First In First Out．
Pythonではdequeがよく使われる．importが必要
code: python
from collections import deque
queue = deque() # 空のキュー（＝スタック）を作成
for i in range(1, 5):
queue.append(i) # 1, 2, 3, 4 がキューに追加
while queue: # while len(queue) > 0: と等価
print(queue.popleft()) # キューの先頭から1つ要素を取り出す
# 出力結果： 1 (改行) 2 (改行) 3 (改行) 4 (改行)
〇 ヒープ（優先度付きキュー）
要素が動的に追加され，最小値を動的に取り出す処理のために利用される．
〇 その他