Go to Qiita Advent Calendar Top
LoginSignup
0
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

@sato_ryo

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

Last updated at Posted at 2025-10-19

注意
(一応人がチェックしてますが）この記事は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 でまとめ出力すると効果的。

参考（提出）

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

参考リンク

0
0
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
0
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?