注意
(一応人がチェックしてますが）この記事はAIに書いてもらいました。

Python競プロ: `defaultdict` / `set` を多用すると遅くなる？実測で検証

問題概要（ABC427 D: The Simple Game）

入力：頂点数 $N$、辺数 $M$、手数パラメータ $k$、各頂点に書かれた文字列 $S$（長さ $N$、各文字は A/B）。有向辺 $(u_i,v_i)$ が $M$ 本与えられ、各頂点の出次数は少なくとも 1。
ルール：駒は 頂点1 から開始。Alice が先手、Alice/Bob が交互に 1 手ずつ動かし、これを 合計 $2k$ 手（=各自 $k$ 手）行う。1 手は「現在頂点から出る辺を 1 本選び遷移」。
勝敗：最終手後に 駒がいる頂点の文字が A なら Alice 勝利、B なら Bob 勝利。
目的：両者最適プレイ時の勝者を求める。

代表的な解法（有限手数ミニマックスDP）

残り手数 $r$ と頂点 $v$ で「Alice が勝てるか」を真偽で持つ。
$\mathrm{dp}[0][v] = (S[v]=='A')$ をベースに、

$r$ が偶数（= Alice 手番）なら $\mathrm{dp}[r][v] = \bigvee_{v\to u}\mathrm{dp}[r-1][u]$（OR）
$r$ が奇数（= Bob 手番）なら $\mathrm{dp}[r][v] = \bigwedge_{v\to u}\mathrm{dp}[r-1][u]$（AND）

ロール配列を使えばメモリ $O(N)$、計算 $O(k(N+M))$。
本記事では、この DP を同一ロジックのまま set/defaultdict を避けて list に置換すると大きく高速化できることを実測で示した。

結論（要点）

隣接リストは list[list[int]] が基本。defaultdict(set) はハッシュのオーバーヘッドで重くなりがち。
DP の状態は set ではなく 0/1 の配列（list）で持つのが安定。
set は「探索が平均 O(1)」でも、確保・再ハッシュ・衝突処理・イテレータ生成などのオーバーヘッドが大きい。層を何度も作る DP では特に効率が悪化。

実験条件

AtCoder ABC427 の「有限手数のゲーム DP」を題材に、以下の2点を入れ替えて計測。

グラフの保持形式：defaultdict(set) vs list[list[int]]
DP 層の保持形式：set vs 0/1配列（list）

※ 先手/後手のミニマックス（A手番=OR、B手番=AND）。各レイヤで全頂点の遷移先を総なめ。
※ 入出力やロール配列などは同水準に調整。

実測結果

グラフの保持	DP層の保持	実行時間（最大）	提出URL
`defaultdict(set)`	`set`（`in`判定）	1514 ms	https://atcoder.jp/contests/abc427/submissions/70287728
`list[list[int]]`	`set`（`in`判定）	1076 ms	https://atcoder.jp/contests/abc427/submissions/70291021
`defaultdict(set)`	0/1配列（`list`）	987 ms	https://atcoder.jp/contests/abc427/submissions/70287881
`list[list[int]]`	0/1配列（`list`）	270 ms	https://atcoder.jp/contests/abc427/submissions/70290910
`list[list[int]]`	0/1配列（`list`） + バルク読み	199 ms	https://atcoder.jp/contests/abc427/submissions/70292304

観察ポイント

DP 層を set → 0/1配列に替えるだけで 1514 → 987 ms（約1.5倍）。
隣接も defaultdict(set) → list[list[int]] に替えると 987 → 270 ms（約3.7倍）。
両方置き換えると ~5.6倍 の改善。

なぜ速くなるのか

set は ハッシュテーブル。各要素は Python オブジェクト参照で、
- ハッシュ計算・衝突処理・リサイズ・イテレータの生成 などが都度コストに。
- 層ごとに set() を新規構築する DP は、層数 × 確保コストが積み上がる。
list の 0/1フラグ配列なら、
- インデックス参照（flags[v]）が軽く、
- 連続メモリで キャッシュ効率 が良い。
隣接を list[list[int]] にすることで、「順次走査 + 短絡（break）」に最適化される。

使い分けの指針

set を使うべきとき
- 集合演算（和・差・交差）が主役。
- 同じ要素をまとめて 1 度だけ扱う（重複の排除）が主目的で、同一の辺や値が大量に混ざる入力を前提とする場合。
list が向くとき（今回）
- 隣接は 全走査で判定（any/all 相当）。
- DP 層は 真偽（0/1） で足りる。
- 層を何度も作り直す（2k 回）ため、軽量な配列が効く。

テンプレ（高速版：O(k·(n+m))）

import sys

def solve():
    it = iter(sys.stdin.buffer.read().split())
    t = int(next(it))
    out = []

    for _ in range(t):
        n = int(next(it)); m = int(next(it)); k = int(next(it))
        S = next(it).decode().strip()

        g = [[] for _ in range(n)]
        for _e in range(m):
            u = int(next(it)) - 1
            v = int(next(it)) - 1
            g[u].append(v)

        prev = bytearray(1 if ch == 'A' else 0 for ch in S)  # r=0

        for r in range(1, 2*k + 1):
            curr = bytearray(n)
            if r % 2 == 0:  # A手番: OR
                for v in range(n):
                    val = 0
                    for u in g[v]:
                        if prev[u]:
                            val = 1; break
                    curr[v] = val
            else:           # B手番: AND
                for v in range(n):
                    val = 1
                    for u in g[v]:
                        if not prev[u]:
                            val = 0; break
                    curr[v] = val
            prev = curr

        out.append('Alice' if prev[0] else 'Bob')

    sys.stdout.write("\\n".join(out))

if __name__ == "__main__":
    solve()

小ネタ

any(prev[u] for u in g[v]) / all(prev[u] for u in g[v]) でも書けるが、内側ループを明示するとジェネレータ生成を避けられて速い。
I/O は sys.stdin.buffer.read() でバルク読みが安定（input() より速い）。
出次数は制約で 1 以上なので特別扱い不要。

まとめ

defaultdict(set) + set の二重ハッシュは 定数倍が重い。
list[list[int]] + list（0/1） に替えるだけで、今回のケースでは 5倍以上 の高速化。
競プロでは 「集合が主役の時だけ set」、「判定は配列で持つ」 を基本指針にするとタイムが安定する。

用語メモ：ミニマックスとロール配列

ミニマックス（minimax）

二人零和の手番ゲームで「先手は自分の有利を最大化（max）」「後手は先手の有利を最小化（min）」するという評価方針。
この問題の有限手数版では、残り手数 $r$・位置 $v$ の“最終的に Alice が勝てるか”を真偽で持ち、

ベース：$\mathrm{dp}[0][v] = (S[v]=='A')$（もう動かない）
A手番（最大化）：$\mathrm{dp}[r][v] = \bigvee_{v\to u}\mathrm{dp}[r-1][u]$（OR）
B手番（最小化）：$\mathrm{dp}[r][v] = \bigwedge_{v\to u}\mathrm{dp}[r-1][u]$（AND）

と遷移する。先読みを全展開する代わりに DP で層ごとに評価していくイメージ。

ロール配列（rolling array）

DP で「直前の層しか参照しない」とき、2次元配列を作らずに 配列2枚（前層 prev と現層 curr）だけを使い回してメモリを削減する手法。
現層を計算し終えたら prev = curr として役割を入れ替え（ロール）る。

prev = bytearray(1 if ch=='A' else 0 for ch in S)  # r=0
for r in range(1, 2*k+1):
    curr = bytearray(n)
    if r % 2 == 0:  # A手番: OR
        for v in range(n):
            val = 0
            for u in g[v]:
                if prev[u]: val = 1; break
            curr[v] = val
    else:           # B手番: AND
        for v in range(n):
            val = 1
            for u in g[v]:
                if not prev[u]: val = 0; break
            curr[v] = val
    prev = curr  # ← ここでロール

補足：バルク読み（bulk I/O）でさらに安定化

大量のトークンを読む問題では、input() を何度も呼ぶより 標準入力を一括で読み込み、
メモリ上で分割して next(it) で順に取得する バルク読み が速くて安定です。

最小差分の置換例

import sys
it = iter(sys.stdin.buffer.read().split())
t = int(next(it))
for _ in range(t):
    n = int(next(it)); m = int(next(it)); k = int(next(it))
    s = next(it).decode()
    # 以降、u = int(next(it)); v = int(next(it)) のように読む

sys.stdin.buffer.read()：一括読み込み（bytes）
.split()：空白（改行・スペース・タブ）で 一括分割
next(it)：必要なトークンを 順に取得（数値は int()、文字列は .decode()）
出力も print の代わりに "\n".join(...) + sys.stdout.write でまとめ出力すると効果的。

参考（提出）

バルク読みを導入した提出: https://atcoder.jp/contests/abc427/submissions/70292304

まとめ：set/defaultdict を避ける＋バルク読みの併用で、同じアルゴリズムでも実行時間をさらに短縮できます。

参考リンク

Stack Overflow：sys.stdin.readline vs input — https://stackoverflow.com/questions/22623528/sys-stdin-readline-and-input-which-one-is-faster-when-reading-lines-of-inpu
Codeforces Blog：Ways for Fast Input / Output in Python — https://codeforces.com/blog/entry/83441
Codeforces Blog：Good Input Template (fast input) — https://codeforces.com/blog/entry/71884
Codeforces Blog：Fast and short Python IO 2024 — https://codeforces.com/blog/entry/124753
Codeforces：buffer.readline が効いた事例 — https://codeforces.com/blog/entry/91991
GeeksforGeeks：Fast I/O for Competitive Programming in Python — https://www.geeksforgeeks.org/python/fast-i-o-for-competitive-programming-in-python/
MCPT Tips：sys.stdin.readline または一括 read — https://mcpt.ca/tips
Python公式ドキュメント：sys.stdin.buffer / sys.stdout — https://docs.python.org/3/library/sys.html#sys.stdin
Codeforces Blog（Fast I/O / テンプレ）— 例: https://codeforces.com/blog/entry/90775
GeeksforGeeks（Fast I/O in Python）— https://www.geeksforgeeks.org/fast-i-o-for-competitive-programming-in-python/