Python AtCoder入門 第12講 collectionsモジュール

Python AtCoder入門 第11講 collectionsモジュール 第10講で辞書と集合を学びました。 この講では、それらをさらに使いやすくする collectionsモジュール を扱います。 1

今回のテーマ 登場するのは3つだけです。 defaultdict Counter deque どれも「なくても書けるが、あると圧倒的に楽になる」道具です。 2

3つの役割 ：キーがなければ初期値を自動で用意する辞書 Counter ：数えることに特化した辞書 deque ：先頭からの取り出しが速いリスト 特に deque は、知らないとTLEになることがあります。 defaultdict 3

コードファイル名の方針 この講でも、コード例ごとにファイル名を付けます。 defaultdict_count.py defaultdict_group.py counter_mode.py anagram.py deque_basic.py answer_11_1.py 4

11-1 collections.defaultdict 第10講で、辞書によるカウント処理を学びました。 count = {} for c in S: count[c] = count.get(c, 0) + 1 get(c, 0) は、キーがまだないかもしれないから必要でした。 5

defaultdictとは 最初から、 キーがないときは0 と決めておける辞書があります。 それが defaultdict です。 from collections import defaultdict count = defaultdict(int) for c in S: count[c] += 1 6

defaultdict(int) count = defaultdict(int) これは、 存在しないキーに触れたら、自動で0を用意する という意味です。 だから、いきなり count[c] += 1 と書けます。 7

読み込み方 defaultdict を使うには、先頭で読み込みます。 from collections import defaultdict 作り方： d = defaultdict(int) d = defaultdict(list) 8

型そのものを渡す 注意点です。 defaultdict(int) と書きます。 defaultdict(0) ではありません。 括弧の中には 型そのもの を書きます。 9

defaultdict_count.py from collections import defaultdict # Read N and the list of N integers N = int(input()) A = list(map(int, input().split())) # Count occurrences without worrying about missing keys count = defaultdict(int) for x in A: count[x] += 1 # Print each value and its count for value, n in count.items(): print(value, n) 10

defaultdict_count.py の実行例 入力例： 7 3 1 4 1 5 3 1 出力例： 3 2 1 3 4 1 5 1 get(x, 0) を書かずに数えられています。 11

defaultdict(list) もう1つの頻出形が、 defaultdict(list) です。 同じキーを持つものをまとめるときに使います。 12

普通の辞書だと if key not in d: d[key] = [] d[key].append(x) のように、先に空リストを用意する必要があります。 defaultdict(list) なら、これが不要になります。 13

いきなりappendできる d[key].append(x) 存在しないキーに触れた瞬間、 [] が自動で用意されます。 グループ分けで非常に便利です。 14

defaultdict_group.py from collections import defaultdict # Read the number of students N = int(input()) # Group student names by their class groups = defaultdict(list) for _ in range(N): name, class_id = input().split() groups[class_id].append(name) # Print each class and its members for class_id, members in groups.items(): print(class_id, *members) 15

defaultdict_group.py の実行例 入力例： 5 Sato A Suzuki B Takahashi A Tanaka C Ito B 出力例： A Sato Takahashi B Suzuki Ito C Tanaka 16

print(class_id, *members) print(class_id, *members) は、 最初にクラス名 そのあとにメンバー名 を空白区切りで出力しています。 第5講の print(*A) の応用です。 17

defaultdictの注意点 には落とし穴があります。 存在しないキーを読んだだけで、そのキーが作られる ことです。 defaultdict d = defaultdict(int) print(d["x"]) print(len(d)) 18

defaultdict_read.py from collections import defaultdict d = defaultdict(int) print(d["x"]) print(len(d)) 出力： 0 1 読んだだけなのに、キー "x" が作られています。 19

存在確認はinを使う 存在確認をしたいだけなら、 if key in d: を使います。 in はキーを作りません。 種類数を数える場面では、余計なキーを作らないように注意します。 20

11-2 collections.Counter カウント処理は非常によく出るので、専用の道具があります。 それが、 Counter です。 数えることに特化した辞書です。 21

Counterの基本 from collections import Counter A = [3, 1, 4, 1, 5, 3, 1] count = Counter(A) print(count) print(count[1]) print(count[99]) 存在しないキーは 0 になります。 22

counter_basic.py from collections import Counter A = [3, 1, 4, 1, 5, 3, 1] count = Counter(A) print(count) print(count[1]) print(count[99]) 出力： Counter({1: 3, 3: 2, 4: 1, 5: 1}) 3 0 23

文字列も数えられる 文字列を渡すと、1文字ずつ数えます。 from collections import Counter count = Counter("banana") print(count["a"]) 出力： 3 24

ループを書かずに数えられる 第10講では、辞書でこう書きました。 count = {} for x in A: count[x] = count.get(x, 0) + 1 Counter(A) なら、リストを渡すだけです。 25

most_common Counter の目玉が、 most_common() です。 出現回数の多い順に並べて返します。 26

most_common.py from collections import Counter count = Counter([3, 1, 4, 1, 5, 3, 1]) print(count.most_common()) print(count.most_common(2)) 出力： [(1, 3), (3, 2), (4, 1), (5, 1)] [(1, 3), (3, 2)] 27

most_commonの戻り値 が返すのは、 値と回数のタプルのリスト です。 most_common() [(値, 回数), ...] 上位1つだけ欲しいなら、 value, n = count.most_common(1)[0] 28

counter_mode.py from collections import Counter # Read N and the list of N integers N = int(input()) A = list(map(int, input().split())) # Count and take the most common one count = Counter(A) value, n = count.most_common(1)[0] print(value, n) 29

counter_mode.py の実行例 入力例： 7 3 1 4 1 5 3 1 出力例： 1 3 1 が3回出ています。 30

most_commonの注意 most_common() は便利です。 ただし、 同数のときにどれが選ばれるかは保証されません。 「同数なら最小の値」などの条件がある問題では、自分で処理します。 31

Counter同士の比較 は、そのまま == で比較できます。 これが効くのが、 アナグラム判定 です。 アナグラムとは、同じ文字を並べ替えて作れる文字列です。 Counter 32

アナグラム判定 from collections import Counter S = "listen" T = "silent" print(Counter(S) == Counter(T)) 出力： True 文字ごとの個数が一致すれば、並べ替えて作れます。 33

anagram.py from collections import Counter # Read two strings S = input() T = input() # Two strings are anagrams if their letter counts match if Counter(S) == Counter(T): print("Yes") else: print("No") 34

anagram.py の実行例 入力例： listen silent 出力例： Yes ループも if の細かい判定も不要です。 35

defaultdict(int) との使い分け 場面 単に数えるだけ リストや文字列を丸ごと渡せる 条件付きで数える 数えながら複雑に加工する 使うもの Counter Counter defaultdict(int) defaultdict(int) 36

判断の目安 基本はこれです。 丸ごと渡せるなら Counter ループの中で条件を挟むなら defaultdict(int) この判断で、ほとんど困りません。 37

11-3 collections.deque ここからは少し性格が違います。 deque は、 知らないとTLEになる 道具です。 リストの先頭から取り出す処理に関係します。 38

リストのpop(0) 第5講で、 pop() を学びました。 A = [3, 1, 4] print(A.pop(0)) print(A) 出力： 3 [1, 4] 先頭の要素を取り出せます。 39

pop(0) は遅い は便利そうですが、遅い操作です。 先頭を抜くと、残り全部を1つずつ前へ詰め直す必要があります。 要素がN個なら、N回の移動が発生します。 A.pop(0) 40

ループで使うとTLE while A: A.pop(0) これをN回繰り返すと、 N × N 回に近い移動が発生します。 N = 100000 なら、確実にTLEです。 41

dequeを使う 先頭から高速に取り出したいときは、 deque を使います。 from collections import deque q = deque([3, 1, 4]) print(q.popleft()) popleft() は先頭から一瞬で取り出します。 42

listとdequeの比較 操作 末尾に追加 末尾から取り出す 先頭に追加 先頭から取り出す list 速い 速い 遅い 遅い deque 速い 速い 速い 速い 先頭を使うなら deque です。 43

dequeの主なメソッド from collections import deque q = deque() q.append(1) q.appendleft(0) print(q.pop()) print(q.popleft()) ：末尾に追加 appendleft ：先頭に追加 pop ：末尾から取り出す popleft ：先頭から取り出す append 44

deque_basic.py from collections import deque # Create a deque from a list q = deque([1, 2, 3]) # Add to both ends q.append(4) q.appendleft(0) print(*q) # Remove from both ends print(q.popleft(), q.pop()) print(*q) # Length and indexing work like a list print(len(q), q[0]) 45

deque_basic.py の出力 0 1 2 3 4 0 4 1 2 3 3 1 len(q) や q[0] はリストと同じように使えます。 46

dequeの注意 deque は、スライスが使えません。 q[1:3] # これはできない 必要なら、リストに変換します。 A = list(q) 47

待ち行列のシミュレーション の典型的な用途は、 先に来たものから順に処理する シミュレーションです。 例： 行列 順番待ち カードの山 先入れ先出し deque 48

queue_simulation.py from collections import deque # Read the number of people and the number of servings N, K = map(int, input().split()) names = input().split() # People wait in a queue queue = deque(names) # Serve K people from the front for _ in range(K): person = queue.popleft() print(person) # Who is still waiting? print(len(queue)) 49

queue_simulation.py の実行例 入力例： 5 3 Sato Suzuki Takahashi Tanaka Ito 出力例： Sato Suzuki Takahashi 2 先頭から3人を処理しています。 50

1文字違いでTLEになる このコードで、 queue.popleft() をリストの queue.pop(0) に置き換えると、大きな入力ではTLEになることがあります。 書き方は似ていますが、速度は大きく違います。 51

pop_speed.py import time from collections import deque N = 100000 # Using a list A = list(range(N)) start = time.time() while A: A.pop(0) print(f"list.pop(0): {time.time() - start:.3f} sec") # Using a deque q = deque(range(N)) start = time.time() while q: q.popleft() print(f"deque.popleft(): {time.time() - start:.3f} sec") 52

pop_speed.py の出力例 list.pop(0): 12.628 sec deque.popleft(): 0.004 sec 実行時間は環境によって変わります。 しかし、差が非常に大きいことは体感できます。 53

while A: while A: は、 Aが空でない間 という意味です。 Pythonでは、 空のリストは False 要素があれば True として扱われます。 54

11-4 データ構造の使い分け 第10講の in の速度差。 この講の pop(0) の速度差。 どちらも、 やりたいことに合った入れ物を選ぶ という話です。 55

使い分け表 やりたいこと 番号でアクセスする 末尾に足す・末尾から取る 先頭から取る・先頭に足す 存在判定を高速にする 重複を消す キーに対応する値を持つ 使うもの list list deque set set dict 56

collectionsを含めた使い分け やりたいこと キーがなければ初期値がほしい 何が何個あるか数える 先頭から高速に取り出す 使うもの defaultdict Counter deque 目的に合わせて選ぶと、コードが短く速くなります。 57

判断の順番 コードを書く前に、次の順で考えます。 1. 番号で取り出したいか → list 2. あるかないかだけ知りたいか → set 3. キーと値の対応がほしいか → dict 4. 先頭から取り出すか → deque 58

問題文のヒント 問題文に次の言葉があったら、 deque を思い出します。 行列 順番待ち 先入れ先出し 左端から取る 右端から取る 両端操作に強いのが deque です。 59

list_vs_deque.py from collections import deque # Read the number of commands N = int(input()) # Version 1: using a list result1 = [] data1 = list(range(1, N + 1)) while data1: result1.append(data1.pop(0)) # Version 2: using a deque result2 = [] data2 = deque(range(1, N + 1)) while data2: result2.append(data2.popleft()) print(*result1) print(*result2) 60

list_vs_deque.py の実行例 入力例： 5 出力例： 1 2 3 4 5 1 2 3 4 5 答えは同じです。 違うのは速度です。 61

章末まとめ collections から次の3つを読み込みます。 from collections import defaultdict, Counter, deque どれも、辞書・リストで書ける処理を短く安全にしてくれます。 62

章末まとめ：defaultdict defaultdict(int) なら、 count[x] += 1 と書けます。 defaultdict(list) なら、 d[key].append(x) でグループ分けできます。 63

章末まとめ：defaultdictの注意 defaultdict(int) のように、型そのものを渡します。 defaultdict(int) ではありません。 また、読んだだけでキーが作られるので、存在確認は in を使います。 defaultdict(0) 64

章末まとめ：Counter Counter(A) は、リストや文字列を渡すだけで数え上げが終わります。 count.most_common(k) で上位k個を取れます。 ただし、同数のときの順序には注意します。 65

章末まとめ：deque リストの pop(0) は遅いです。 先頭から取り出すなら、 deque を使います。 append appendleft pop popleft が基本です。 66

章末まとめ：使い分け 丸ごと数える → Counter 条件付きで数える → defaultdict(int) グループ分け → defaultdict(list) 先頭から取り出す → deque 道具を選ぶだけで、コードも速度も変わります。 67

練習問題 11-1 最も多い文字 英小文字からなる文字列 S が与えられます。 最も多く出現する文字と、その出現回数を出力してください。 最も多い文字が複数ある場合は、 辞書順で最も小さいもの を出力します。 68

練習問題 11-1：入力と出力 入力例： banana 出力例： a 3 a が3回出ています。 69

answer_11_1.py from collections import Counter # Read a string S = input() # Count the characters count = Counter(S) # Find the most frequent character best_char = "" best_count = 0 for c, n in count.items(): if n > best_count: best_char = c best_count = n elif n == best_count and c < best_char: best_char = c print(best_char, best_count) 70

answer_11_1.py のポイント most_common() は同数のときの順序が保証されません。 この問題では、 同数なら辞書順で最小 という条件があります。 そのため、自分で更新条件を書いています。 71

練習問題 11-2 同じ点数の生徒 N人の生徒の名前と点数が与えられます。 同じ点数の生徒が2人以上いる点数について、 点数と生徒名を入力順に出力してください。 出力順は、点数の小さい順です。 72

練習問題 11-2：入力と出力 入力例： 5 Sato 80 Suzuki 60 Takahashi 80 Tanaka 45 Ito 60 出力例： 60 Suzuki Ito 80 Sato Takahashi 73

answer_11_2.py from collections import defaultdict # Read the number of students N = int(input()) # Group student names by their score groups = defaultdict(list) for _ in range(N): name, score = input().split() groups[int(score)].append(name) # Print scores with two or more students for score in sorted(groups): if len(groups[score]) >= 2: print(score, *groups[score]) 74

answer_11_2.py のポイント 点数をキーにして、名前をリストに溜めます。 groups[int(score)].append(name) 入力順に append するので、名前は自然に入力順になります。 出力は sorted(groups) で点数順にします。 75

練習問題 11-3 カードゲーム N枚のカードが1列に並んでいます。 太郎さんと次郎さんが交互にカードを取ります。 太郎さんは左端から取る 次郎さんは右端から取る 太郎さんから先に取る それぞれの合計を出力してください。 76

練習問題 11-3：入力と出力 入力例： 5 3 1 4 1 5 出力例： 8 6 太郎： 3 + 1 + 4 = 8 次郎： 5 + 1 = 6 77

answer_11_3.py from collections import deque # Read N and the cards N = int(input()) queue = deque(map(int, input().split())) # Taro takes from the left, Jiro takes from the right taro = 0 jiro = 0 while queue: taro += queue.popleft() if not queue: break jiro += queue.pop() print(taro, jiro) 78

answer_11_3.py のポイント 左端から取るので、 popleft() 右端から取るので、 pop() を使います。 カードが奇数枚の場合、太郎が最後の1枚を取ったあとに止める必要があります。 79

第11講まとめ この講では、 collectionsモジュール を学びました。 defaultdict 、 Counter 、 deque は、B問題で非常によく使う便利な道具です。 80

次回予告 次の第12講では、 itertoolsモジュール を扱います。 第4講で書いた「二重ループですべてのペアを調べる」処理が、専用の道具で書けるようになります。 81