---
title: Python AtCoder入門 第10講 辞書(dict)と集合(set)
tags: 
author: [佐藤](https://image.docswell.com/user/aomori_sato)
site: [Docswell](https://www.docswell.com/)
thumbnail: https://bcdn.docswell.com/page/VENYP154J8.jpg?width=480
description: Python AtCoder入門 第10講 辞書(dict)と集合(set) by 佐藤
published: September 23, 26
canonical: https://image.docswell.com/s/aomori_sato/K4NR1D-2026-09-23-145319
---
# Page. 1

![Page Image](https://bcdn.docswell.com/page/VENYP154J8.jpg)

Python AtCoder入門
第10講 辞書(dict)と集合(set)
ここから 第3部「道具を増やす」 に入ります。
第2部までで、AtCoderのA問題・B問題を解くための基礎は一通り揃いました。
1


# Page. 2

![Page Image](https://bcdn.docswell.com/page/Y79P35Y4E3.jpg)

今回のテーマ
ここまでの知識だけでも、多くの問題は解けます。
しかし、
「解ける」と「速く正確に解ける」の間には、まだ大きな差があります。
第3部では、その差を埋めます。
2


# Page. 3

![Page Image](https://bcdn.docswell.com/page/G78DMY6V7D.jpg)

辞書と集合
この講で扱うのは、
辞書 dict
集合 set
です。
リストと二重ループで頑張れば書ける処理が、正しい道具を使うと数行で速く書けます。
3


# Page. 4

![Page Image](https://bcdn.docswell.com/page/L7LM349RJR.jpg)

コードファイル名の方針
この講でも、コード例ごとにファイル名を付けます。
dict_basic.py
count_chars.py
tuple_key.py
set_basic.py
set_speed.py
answer_10_1.py
4


# Page. 5

![Page Image](https://bcdn.docswell.com/page/4EMYDKZPEW.jpg)

10-1 辞書の基本
リストは、
番号で中身を取り出す
入れ物でした。
A = [30, 10, 40]
print(A[0])
出力：
30
5


# Page. 6

![Page Image](https://bcdn.docswell.com/page/PER94X6YJ9.jpg)

辞書とは
辞書は、
名前で中身を取り出す
入れ物です。
scores = {"Sato": 80, "Suzuki": 45}
print(scores["Sato"])
出力：
80
6


# Page. 7

![Page Image](https://bcdn.docswell.com/page/P7XQ26M4EX.jpg)

辞書の形
辞書は { } で作ります。
scores = {"Sato": 80, "Suzuki": 45}
中身は、
キー: 値
の形で並べます。
7


# Page. 8

![Page Image](https://bcdn.docswell.com/page/37K9M1GP7D.jpg)

何に使うか
辞書は、次のようなデータに向いています。
名前と点数
文字と出現回数
座標と状態
「0番目、1番目」という並びより、
何に対応する値か
が大事なときに使います。
8


# Page. 9

![Page Image](https://bcdn.docswell.com/page/LJ3WYQN4J5.jpg)

追加と更新
scores = {}
scores["Sato"] = 80
scores["Sato"] = 90
print(scores)
出力：
{'Sato': 90}
存在しないキーなら追加、存在するキーなら上書きです。
9


# Page. 10

![Page Image](https://bcdn.docswell.com/page/8JDK59W5EG.jpg)

削除
辞書から要素を削除するには del を使います。
scores = {"Sato": 80}
del scores["Sato"]
print(scores)
出力：
{}
10


# Page. 11

![Page Image](https://bcdn.docswell.com/page/VEPKGZ9D78.jpg)

キーの存在判定
キーがあるかどうかは in で調べます。
scores = {"Sato": 80}
print("Sato" in scores)
print("Tanaka" in scores)
出力：
True
False
11


# Page. 12

![Page Image](https://bcdn.docswell.com/page/27VV6WMG7Q.jpg)

KeyError
存在しないキーを読もうとすると、エラーになります。
scores = {"Sato": 80}
print(scores["Tanaka"])
KeyError
このエラーは辞書でよく出ます。
12


# Page. 13

![Page Image](https://bcdn.docswell.com/page/5JGLNDXD7L.jpg)

get
get()
を使うと、キーがなくてもエラーになりません。
scores = {"Sato": 80}
print(scores.get("Tanaka", 0))
print(scores.get("Sato", 0))
出力：
0
80
13


# Page. 14

![Page Image](https://bcdn.docswell.com/page/47QYQ18XEP.jpg)

getの形
d.get(キー, 初期値)
キーがあれば、その値を返します。
キーがなければ、指定した初期値を返します。
カウント処理でとても便利です。
14


# Page. 15

![Page Image](https://bcdn.docswell.com/page/KE4WNR22J1.jpg)

カウントの定石
d[c] = d.get(c, 0) + 1
これは、
あればその値、なければ0に、1を足す
という意味です。
if c in d: で分岐を書く必要がなくなります。
15


# Page. 16

![Page Image](https://bcdn.docswell.com/page/L71Y5QMKJG.jpg)

辞書のループ
辞書を for で回すと、キーだけが取り出されます。
scores = {"Sato": 80, "Suzuki": 45}
for name in scores:
print(name, scores[name])
16


# Page. 17

![Page Image](https://bcdn.docswell.com/page/G7WG5M3PE2.jpg)

items
キーと値を同時に取り出すなら、 items() を使います。
for name, score in scores.items():
print(name, score)
は、キーと値のタプルを順に返します。
それをアンパックしています。
items()
17


# Page. 18

![Page Image](https://bcdn.docswell.com/page/4JZLNQV6E3.jpg)

keys と values
辞書には次のメソッドもあります。
keys() ：キーだけ
values() ：値だけ
items() ：キーと値
たとえば、
sum(scores.values())
で値の合計が取れます。
18


# Page. 19

![Page Image](https://bcdn.docswell.com/page/YE6W865LEV.jpg)

dict_basic.py
# Create a dictionary
scores = {"Sato": 80, "Suzuki": 45}
# Add and update
scores["Takahashi"] = 72
scores["Suzuki"] = 60
# Access and check
print(scores["Sato"])
print("Tanaka" in scores)
print(scores.get("Tanaka", 0))
# Iterate over keys and values
for name, score in scores.items():
print(name, score)
# Aggregate the values
print(sum(scores.values()))
19


# Page. 20

![Page Image](https://bcdn.docswell.com/page/GE5M96YME4.jpg)

dict_basic.py の出力
80
False
0
Sato 80
Suzuki 60
Takahashi 72
212
辞書の基本操作をまとめて確認できます。
20


# Page. 21

![Page Image](https://bcdn.docswell.com/page/97292MGRJR.jpg)

count_chars.py
# Read a string
S = input()
# Count each character
count = {}
for c in S:
count[c] = count.get(c, 0) + 1
# Print in the order the characters first appeared
for c, n in count.items():
print(c, n)
21


# Page. 22

![Page Image](https://bcdn.docswell.com/page/DJY4YXV57M.jpg)

count_chars.py の実行例
入力例：
banana
出力例：
b 1
a 3
n 2
「何が何個あるか」を数える典型例です。
22


# Page. 23

![Page Image](https://bcdn.docswell.com/page/V7NYP1M4E8.jpg)

辞書は探す手間を消す
リストで同じことをしようとすると、
値の種類ごとに探し直すことになりがちです。
辞書なら、キーに対応する値を直接更新できます。
辞書は「探す」という手間そのものを消してくれます。
23


# Page. 24

![Page Image](https://bcdn.docswell.com/page/YJ9P35N473.jpg)

辞書は追加順を覚えている
Pythonの辞書は、追加した順序を覚えています。
そのため、
banana
を数えると、
b, a, n
の順に出力されます。
文字が最初に現れた順です。
24


# Page. 25

![Page Image](https://bcdn.docswell.com/page/GJ8DMYKVJD.jpg)

10-2 辞書のキーに使えるもの
辞書のキーに使えるのは、
変更できないもの
だけです。
第6講で学んだイミュータブルな値です。
25


# Page. 26

![Page Image](https://bcdn.docswell.com/page/LJLM34ZRER.jpg)

キーに使える型
型
int
str
tuple
list
キーに使えるか
○
○
○
×
リストは中身が変わる可能性があるので、キーにできません。
26


# Page. 27

![Page Image](https://bcdn.docswell.com/page/47MYDKVP7W.jpg)

tupleはOK、listはNG
d = {}
d[(1, 2)] = "ok"
d[[1, 2]] = "ng"
1行目はOKです。
2行目は TypeError になります。
27


# Page. 28

![Page Image](https://bcdn.docswell.com/page/P7R94X2YE9.jpg)

座標をキーにする
タプルがキーに使えることの大きな利点は、
座標を直接扱える
ことです。
board = {}
board[(3, 5)] = "#"
board[(-100, 2000000)] = "#"
28


# Page. 29

![Page Image](https://bcdn.docswell.com/page/PJXQ26D47X.jpg)

広い座標でも扱える
座標の範囲が非常に広い場合、2次元リストは作れません。
たとえば、
-10^9 <= x <= 10^9
のような範囲です。
辞書なら、実際に使った座標だけを保存できます。
29


# Page. 30

![Page Image](https://bcdn.docswell.com/page/3JK9M1XPJD.jpg)

getで空白マスを表す
board = {}
board[(3, 5)] = "#"
print(board.get((3, 5), "."))
print(board.get((0, 0), "."))
出力：
#
.
置かれていないマスは "." として扱えます。
30


# Page. 31

![Page Image](https://bcdn.docswell.com/page/LE3WYQ54E5.jpg)

tuple_key.py
# Read the number of points
N = int(input())
# Count how many times each coordinate appears
count = {}
for _ in range(N):
x, y = map(int, input().split())
count[(x, y)] = count.get((x, y), 0) + 1
# Print coordinates that appear more than once
for (x, y), n in count.items():
if n >= 2:
print(x, y, n)
31


# Page. 32

![Page Image](https://bcdn.docswell.com/page/8EDK59D57G.jpg)

tuple_key.py の実行例
入力例：
5
1 2
3 4
1 2
5 6
1 2
出力例：
1 2 3
座標 (1, 2) が3回出ています。
32


# Page. 33

![Page Image](https://bcdn.docswell.com/page/V7PKGZXDJ8.jpg)

キーもアンパックできる
for (x, y), n in count.items():
ここでは、
キー (x, y) を x と y にアンパック
値を n に代入
しています。
第6講のアンパックの応用です。
33


# Page. 34

![Page Image](https://bcdn.docswell.com/page/2JVV6WLGJQ.jpg)

10-3 集合の基本
集合 set は、
重複を許さない、順序のない集まり
です。
辞書から値を取り除いて、キーだけにしたものと考えるとわかりやすいです。
34


# Page. 35

![Page Image](https://bcdn.docswell.com/page/5EGLND3DJL.jpg)

集合の例
s = {3, 1, 4, 1, 5}
print(s)
出力例：
{1, 3, 4, 5}
重複した 1 が消えています。
順序は保証されません。
35


# Page. 36

![Page Image](https://bcdn.docswell.com/page/4JQYQ15X7P.jpg)

集合の作り方
s = {3, 1, 4}
s = set()
s = set([3, 1, 4, 1])
注意：
{}
は空の集合ではありません。
空の辞書です。
36


# Page. 37

![Page Image](https://bcdn.docswell.com/page/K74WNR92E1.jpg)

空の集合
空の集合を作るときは、
s = set()
です。
s = {}
と書くと、辞書になります。
ここはよく間違えます。
37


# Page. 38

![Page Image](https://bcdn.docswell.com/page/LJ1Y5QKKEG.jpg)

追加・削除・判定
s = set()
s.add(3)
s.add(3)
print(len(s))
s.discard(3)
print(3 in s)
出力：
1
False
同じものを追加しても1つのままです。
38


# Page. 39

![Page Image](https://bcdn.docswell.com/page/GJWG5MDP72.jpg)

discard と remove
集合には remove() もあります。
しかし、存在しない値を消そうとすると KeyError になります。
s.discard(x)
なら、存在しなくてもエラーになりません。
安全に消すなら discard() です。
39


# Page. 40

![Page Image](https://bcdn.docswell.com/page/4EZLNQG673.jpg)

用途1：重複の除去
リストから重複を消して種類数を数えるなら、集合です。
A = [3, 1, 4, 1, 5, 9, 2, 6, 5]
print(len(set(A)))
出力：
7
40


# Page. 41

![Page Image](https://bcdn.docswell.com/page/Y76W86YL7V.jpg)

用途2：集合演算
数学の集合と同じ演算ができます。
演算
記号
和集合 `A
積集合 A & B
差集合 A - B
意味
B`
両方に含まれる
Aにあり、Bにない
41


# Page. 42

![Page Image](https://bcdn.docswell.com/page/G75M96GM74.jpg)

set_operations.py
A = {1, 2, 3, 4}
B = {3, 4, 5}
print(A | B)
print(A & B)
print(A - B)
出力例：
{1, 2, 3, 4, 5}
{3, 4}
{1, 2}
42


# Page. 43

![Page Image](https://bcdn.docswell.com/page/9J292MYRER.jpg)

set_basic.py
# Read N and the list of N integers
N = int(input())
A = list(map(int, input().split()))
# Number of distinct values
print(len(set(A)))
# Are all the values distinct?
if len(set(A)) == N:
print("Yes")
else:
print("No")
43


# Page. 44

![Page Image](https://bcdn.docswell.com/page/DEY4YXG5JM.jpg)

set_basic.py の実行例
入力例：
6
3 1 4 1 5 9
出力例：
5
No
1
が重複しているので、すべて異なるわけではありません。
44


# Page. 45

![Page Image](https://bcdn.docswell.com/page/VJNYP1G478.jpg)

重複がないか判定する定石
len(set(A)) == len(A)
なら、すべての要素が異なります。
「全要素が異なるか」を問う問題でよく使います。
45


# Page. 46

![Page Image](https://bcdn.docswell.com/page/YE9P35W4J3.jpg)

common_values.py
# Read the two lists
N = int(input())
A = set(map(int, input().split()))
M = int(input())
B = set(map(int, input().split()))
# Common values
print(len(A & B))
# Values only in A
print(len(A - B))
# All distinct values
print(len(A | B))
46


# Page. 47

![Page Image](https://bcdn.docswell.com/page/GE8DMYNVED.jpg)

common_values.py の実行例
入力例：
5
1 2 3 4 5
4
3 4 5 6
出力例：
3
2
6
入力時点で set(...) にしています。
47


# Page. 48

![Page Image](https://bcdn.docswell.com/page/LELM34PR7R.jpg)

10-4 in の速度差
この節が、本講で最も重要です。
同じ in でも、
リストに使う場合 と 集合・辞書に使う場合
では速度が大きく違います。
48


# Page. 49

![Page Image](https://bcdn.docswell.com/page/4JMYDK4PJW.jpg)

リストのinは遅い
リストの in は、先頭から順に探します。
要素がN個あれば、最悪N回の比較が必要です。
x in A
Aがリストなら、要素数に比例して時間がかかります。
49


# Page. 50

![Page Image](https://bcdn.docswell.com/page/PJR94XWY79.jpg)

集合・辞書のinは速い
集合と辞書の in は、要素数が多くてもほぼ一瞬です。
中身を順に調べるのではなく、
値から直接場所を計算する仕組み
になっているためです。
50


# Page. 51

![Page Image](https://bcdn.docswell.com/page/PEXQ26P4JX.jpg)

inの速さ
データ構造 in の速さ
リスト
遅い
集合
速い
辞書
速い
ループの中で使うと、この差が大きく出ます。
51


# Page. 52

![Page Image](https://bcdn.docswell.com/page/3EK9M1DPED.jpg)

危険な例
for x in A:
if x in B:
count += 1
もし B がリストなら、毎回Bの中を探します。
N = 100000 , M = 100000 なら、最大で100億回の比較です。
TLEになります。
52


# Page. 53

![Page Image](https://bcdn.docswell.com/page/L73WYQR475.jpg)

対策はsetにするだけ
B = set(B)
for x in A:
if x in B:
count += 1
これだけで、 in が高速になります。
100億回の比較が、10万回程度になります。
53


# Page. 54

![Page Image](https://bcdn.docswell.com/page/87DK59Y5JG.jpg)

鉄則
ループの中で in を使うなら、相手を集合にする。
B = set(B)
この1行で、TLEがACに変わることがあります。
54


# Page. 55

![Page Image](https://bcdn.docswell.com/page/VJPKGZ6DE8.jpg)

set_speed.py
import time
# Prepare 100000 values
N = 100000
data = list(range(N))
data_set = set(data)
# Search 10000 times in a list
start = time.time()
for i in range(10000):
_ = (N - 1) in data
print(f"list: {time.time() - start:.3f} sec")
# Search 10000 times in a set
start = time.time()
for i in range(10000):
_ = (N - 1) in data_set
print(f"set: {time.time() - start:.3f} sec")
55


# Page. 56

![Page Image](https://bcdn.docswell.com/page/2EVV6W3GEQ.jpg)

set_speed.py の出力例
list: 7.316 sec
set: 0.001 sec
実行時間は環境によって変わります。
しかし、リストと集合で大きな差が出ることは体感できます。
56


# Page. 57

![Page Image](https://bcdn.docswell.com/page/57GLNDYDEL.jpg)

第3部の主題
アルゴリズムを大きく変えなくても、
データ構造を変えるだけで速くなる
ことがあります。
これが第3部の主題です。
「解ける」から「速く正確に解ける」へ進みます。
57


# Page. 58

![Page Image](https://bcdn.docswell.com/page/4EQYQ1MXJP.jpg)

使い分けの整理
やりたいこと
順番に並べる
番号でアクセスする
存在判定を高速にする
重複を消す
キーに対応する値を持つ
何が何個あるか数える
使うもの
リスト
リスト
集合
集合
辞書
辞書
58


# Page. 59

![Page Image](https://bcdn.docswell.com/page/KJ4WNRV271.jpg)

判断の基準
迷ったら、次で考えます。
番号で取り出したいか
名前で取り出したいか
あるかないかだけ知りたいか
何個あるか数えたいか
目的に合う道具を選びましょう。
59


# Page. 60

![Page Image](https://bcdn.docswell.com/page/LE1Y5Q3K7G.jpg)

章末まとめ：辞書
辞書は、
{キー: 値}
で作ります。
番号ではなく、名前で中身を取り出す入れ物です。
追加も更新も、
d[key] = value
です。
60


# Page. 61

![Page Image](https://bcdn.docswell.com/page/GEWG5MPPJ2.jpg)

章末まとめ：get
存在しないキーを読むと KeyError になります。
安全に読むなら、
d.get(key, default)
カウントの定石は、
d[x] = d.get(x, 0) + 1
です。
61


# Page. 62

![Page Image](https://bcdn.docswell.com/page/47ZLNQK6J3.jpg)

章末まとめ：辞書のループ
で辞書を回すと、キーだけが取れます。
キーと値の両方を使うなら、
for
for key, value in d.items():
です。
値だけなら d.values() が使えます。
62


# Page. 63

![Page Image](https://bcdn.docswell.com/page/YJ6W86QLJV.jpg)

章末まとめ：キーに使えるもの
辞書のキーに使えるのは、変更できないものです。
数値
文字列
タプル
リストはキーにできません。
タプルをキーにすると、座標を直接扱えます。
63


# Page. 64

![Page Image](https://bcdn.docswell.com/page/GJ5M96RMJ4.jpg)

章末まとめ：集合
集合は、重複を許さない集まりです。
s = set()
空の集合は {} ではなく set() です。
set(A) で重複を消せます。
64


# Page. 65

![Page Image](https://bcdn.docswell.com/page/LE3WYQP9E5.jpg)

章末まとめ：集合演算
集合演算は次の通りです。
A | B ：和集合
A & B ：積集合
A - B ：差集合
共通要素や片方にしかない要素を簡単に求められます。
65


# Page. 66

![Page Image](https://bcdn.docswell.com/page/8EDK59L87G.jpg)

章末まとめ：inの速度
リストの in は遅いです。
集合・辞書の in は速いです。
ループの中で in を使うなら、相手を集合にする。
これは鉄則です。
66


# Page. 67

![Page Image](https://bcdn.docswell.com/page/V7PKGZ2WJ8.jpg)

練習問題 10-1 共通して持っているもの
太郎さんはN個のカードを、次郎さんはM個のカードを持っています。
カードには整数が書かれています。
両方が持っている整数の種類数 を出力してください。
67


# Page. 68

![Page Image](https://bcdn.docswell.com/page/2JVV6WD9JQ.jpg)

練習問題 10-1：入力と出力
入力例：
5
1 2 3 4 5
4
3 4 5 6
出力例：
3
共通するのは 3 , 4 , 5 です。
68


# Page. 69

![Page Image](https://bcdn.docswell.com/page/5EGLNDY4JL.jpg)

answer_10_1.py
# Read the two card sets
N = int(input())
A = set(map(int, input().split()))
M = int(input())
B = set(map(int, input().split()))
# Values that appear in both
print(len(A & B))
集合の積集合を使います。
69


# Page. 70

![Page Image](https://bcdn.docswell.com/page/4JQYQ1MR7P.jpg)

answer_10_1_loop.py
# Read the two card sets
N = int(input())
A = set(map(int, input().split()))
M = int(input())
B = set(map(int, input().split()))
count = 0
for x in A:
if x in B:
count += 1
print(count)
B
が集合なので、 in が高速です。
70


# Page. 71

![Page Image](https://bcdn.docswell.com/page/K74WNRVQE1.jpg)

練習問題 10-2 最も多く出た数
N個の整数が与えられます。
最も多く出現した整数と、その出現回数を出力してください。
同じ回数のものが複数ある場合は、
そのうち最小のもの
を出力します。
71


# Page. 72

![Page Image](https://bcdn.docswell.com/page/LJ1Y5Q3LEG.jpg)

練習問題 10-2：入力と出力
入力例：
7
3 1 4 1 5 3 1
出力例：
1 3
1
が3回出ています。
72


# Page. 73

![Page Image](https://bcdn.docswell.com/page/GJWG5MPQ72.jpg)

answer_10_2.py
# Read N and the list of N integers
N = int(input())
A = list(map(int, input().split()))
# Count occurrences
count = {}
for x in A:
count[x] = count.get(x, 0) + 1
# Find the most frequent value
best_value = -1
best_count = 0
for value, n in count.items():
if n > best_count:
best_value = value
best_count = n
elif n == best_count and value < best_value:
best_value = value
print(best_value, best_count)
73


# Page. 74

![Page Image](https://bcdn.docswell.com/page/4EZLNQK373.jpg)

answer_10_2.py のポイント
更新条件は2段階です。
出現回数が多ければ更新
出現回数が同じなら、値が小さいときだけ更新
値の範囲が広いので、個数管理には辞書を使います。
74


# Page. 75

![Page Image](https://bcdn.docswell.com/page/Y76W86QZ7V.jpg)

練習問題 10-3 初めて重複する位置
N個の整数が与えられます。
先頭から順に見たとき、
それまでに出てきた整数と同じものが初めて現れる位置
を1始まりで出力してください。
最後まで重複がなければ -1 です。
75


# Page. 76

![Page Image](https://bcdn.docswell.com/page/G75M96R974.jpg)

練習問題 10-3：入力と出力
入力例：
6
3 1 4 1 5 9
出力例：
4
4番目の 1 が、2番目の 1 と重複しています。
76


# Page. 77

![Page Image](https://bcdn.docswell.com/page/9J292MD5ER.jpg)

answer_10_3.py
# Read N and the list of N integers
N = int(input())
A = list(map(int, input().split()))
# Remember the values we have seen so far
seen = set()
answer = -1
for i, x in enumerate(A, 1):
if x in seen:
answer = i
break
seen.add(x)
print(answer)
77


# Page. 78

![Page Image](https://bcdn.docswell.com/page/DEY4YX26JM.jpg)

answer_10_3.py のポイント
「それまでに出てきたもの」を集合で管理します。
seen = set()
は、重複判定の後に書きます。
先に追加すると、自分自身と重複してしまいます。
seen.add(x)
78


# Page. 79

![Page Image](https://bcdn.docswell.com/page/VJNYP1W178.jpg)

第10講まとめ
この講では、
辞書と集合
を学びました。
どちらも、B問題を速く正確に解くための重要な道具です。
79


# Page. 80

![Page Image](https://bcdn.docswell.com/page/YE9P35XYJ3.jpg)

次回予告
次の第11講では、
collectionsモジュール
を扱います。
この講で書いた、
d.get(c, 0) + 1
というカウント処理が、さらに短く書けるようになります。
80