競プロ早見表

Python 25 topics · 印刷対応 (A4)
各項目は 使う場面 → 図解 → コード → 罠 の順。// 灰色はコメント、計算量は右上。
データ構造 Union-Find 素集合・連結判定 ほぼ O(α(N))

経路圧縮 + size 併合。連結判定 / グループ分け / Kruskal。union は併合したら true。

init   0  1  2  3  4   (各自が根)
u(0,1) 0──1  2  3  4
u(2,3) 0──1  2──3  4
u(1,2) 0──1──2──3  4   same(0,3)=T size=4
find: 根まで辿り親を直付け(経路圧縮)
class UnionFind:
    def __init__(self, n):
        self.par = list(range(n))
        self.sz = [1] * n
    def find(self, x):
        while self.par[x] != x:
            self.par[x] = self.par[self.par[x]]   # 経路圧縮(半分)
            x = self.par[x]
        return x
    def union(self, a, b):
        ra, rb = self.find(a), self.find(b)
        if ra == rb:
            return False
        if self.sz[ra] < self.sz[rb]:
            ra, rb = rb, ra
        self.par[rb] = ra
        self.sz[ra] += self.sz[rb]
        return True
    def same(self, a, b):
        return self.find(a) == self.find(b)
    def size(self, x):
        return self.sz[self.find(x)]
  • size(小)を size(大)に繋ぐ(union by size)で木を低く保つ
  • 辺の削除はできない(追加のみ)。削除込みは別手法
データ構造 BIT (Fenwick) 点加算 + 区間和 / 転倒数 O(log N)

点加算・前方和を O(log N)。転倒数は「右より小さい既出要素の総数」で求まる。

idx は (i & -i) 幅を管理
add(i,v): x += x & -x で上る
sum(i):   x -= x & -x で下り a[0..i] の和
区間 [l,r] = sum(r) - sum(l-1)
転倒数: 後ろから add しつつ sum(a[i]-1)
class BIT:
    def __init__(self, n):
        self.n = n
        self.t = [0] * (n + 1)
    def add(self, i, v):
        x = i + 1
        while x <= self.n:
            self.t[x] += v
            x += x & -x
    def sum(self, i):                 # a[0..i]
        x, s = i + 1, 0
        while x > 0:
            s += self.t[x]
            x -= x & -x
        return s

def inversions(a):
    bit = BIT((max(a) if a else 0) + 1)
    res = 0
    for x in reversed(a):
        if x > 0:
            res += bit.sum(x - 1)
        bit.add(x, 1)
    return res
  • 1-indexed で持つ(内部 x=i+1)。0 を add する値域に注意
  • 区間和は IntArray.sum() でなく Long で(溢れ)
グラフ Dijkstra 法 単一始点・非負重み最短路 O((V+E) log V)

優先度キューで未確定のうち最小距離の頂点を順に確定。負辺があると使えない(→Bellman-Ford)。

(0)──5──▶(1)   start = 0
 │        ▲    init  dist=[0, ∞, ∞]
 2        1    pop0  1=5 2=2 →[0,5,2]
 ▼        │    pop2  1=2+1=3 →[0,3,2]
(2)───────┘    pop1  settled
0▶1:5 0▶2:2 2▶1:1      ans [0,3,2]
import heapq
# g[v] = list of (to, cost)
def dijkstra(g, s):
    dist = [float('inf')] * len(g); dist[s] = 0
    pq = [(0, s)]                       # (dist, vertex)
    while pq:
        d, v = heapq.heappop(pq)
        if d > dist[v]:
            continue                    # 古い距離は捨てる
        for to, c in g[v]:
            if d + c < dist[to]:
                dist[to] = d + c
                heapq.heappush(pq, (dist[to], to))
    return dist
  • if (d > dist[v]) continue を必ず入れる(古い距離を捨てる、無いと TLE)
  • INF は加算で溢れない値に。C++ 4e18 / 他 LONG_MAX/4
  • 経路復元は prev[to]=v を更新し終点から逆順
グラフ グリッド BFS 迷路・最少手数 O(HW)

4 近傍を距離 +1 で push。壁 # と訪問済みは skip。最短手数 = 到達時の dist。

grid (#=壁)        dist from S
S . . #            0 1 2 #
. # . .            1 # 3 4
. . . G            2 3 4 5
4近傍↑↓←→を BFS → G = 5
from collections import deque
def grid_bfs(grid, sy, sx):
    h, w = len(grid), len(grid[0])
    dist = [[-1] * w for _ in range(h)]
    dist[sy][sx] = 0
    q = deque([(sy, sx)])
    while q:
        y, x = q.popleft()
        for dy, dx in ((-1, 0), (1, 0), (0, -1), (0, 1)):
            ny, nx = y + dy, x + dx
            if not (0 <= ny < h and 0 <= nx < w):
                continue
            if grid[ny][nx] == '#' or dist[ny][nx] != -1:
                continue
            dist[ny][nx] = dist[y][x] + 1
            q.append((ny, nx))
    return dist
  • 到達不可は -1 のまま
  • 8 近傍や重み付きは別 (重みは 0-1 BFS / Dijkstra)
ユーティリティ 累積和 / いもす法 区間和 O(1) / 区間加算 前計算 O(N), クエリ O(1)

累積和で区間和を O(1)。逆操作のいもす法は「区間加算を大量 → 最後に復元」。

a   = [1 2 3 4 5]
sum = [0 1 3 6 10 15]   (1個ずれ)
区間 [l,r) = sum[r] - sum[l]   [1,4)=9
いもす: add(l,r,v)= diff[l]+=v; diff[r]-=v
        最後に累積和で復元
from itertools import accumulate
def prefix_sum(a):                          # s[i]=a[0..i-1]; [l,r)=s[r]-s[l]
    return list(accumulate(a, initial=0))

class Imos:
    def __init__(self, n):
        self.diff = [0] * (n + 1)
    def add(self, l, r, v):                 # a[l..r-1] += v
        self.diff[l] += v
        self.diff[r] -= v
    def build(self):
        return list(accumulate(self.diff))[:-1]
  • sum は長さ N+1。区間は半開 [l, r) で扱うと添字ミスが減る
  • いもす法は右端 r を「含まない」位置に -v
数学 mod 演算 / nCr modpow・modinv・組合せ O(log N) / 前計算 O(N)

modpow は繰返し二乗法。modinv はフェルマー(m素数で a^(m-2))。nCr は階乗逆元の前計算。

modpow(a,e): e を 2 進で繰返し二乗
  a^13 = a^8 · a^4 · a^1   (13 = 1101)
modinv(a) = a^(m-2) mod m   (m 素数)
nCr = fact[n]·inv[r]·inv[n-r]   前計算 O(n)
MOD = 998244353                          # or 10**9 + 7
def modpow(a, e, m=MOD):
    return pow(a, e, m)                  # 組み込み pow が高速
def modinv(a, m=MOD):
    return pow(a, m - 2, m)              # m は素数
class Comb:
    def __init__(self, max_n, m=MOD):
        self.m = m
        self.fact = [1] * (max_n + 1)
        for i in range(1, max_n + 1):
            self.fact[i] = self.fact[i - 1] * i % m
        self.inv = [1] * (max_n + 1)
        self.inv[max_n] = pow(self.fact[max_n], m - 2, m)
        for i in range(max_n, 0, -1):
            self.inv[i - 1] = self.inv[i] * i % m
    def nCr(self, n, r):
        if r < 0 or r > n:
            return 0
        return self.fact[n] * self.inv[r] % self.m * self.inv[n - r] % self.m
  • MOD は問題指定 (998244353 か 1e9+7) を必ず確認
  • 掛け算ごとに % を取る(2 回掛けたら溢れる手前で)
  • Python は組み込み pow(a,e,m) が最速
数学 エラトステネスの篩 素数列挙 O(N log log N)

isPrime[i] を一括計算。i*i から消すのがポイント。約数/素因数のクエリが多いなら最小素因数表へ。

2 3 4 5 6 7 8 9 10 ...
2の倍数除外 → 3の → 5の → ...
消す開始は i*i (それ未満は既出)
残り = 素数  例) ~20: 2 3 5 7 11 13 17 19
def sieve(n):                          # is_prime[i]
    p = [True] * (n + 1)
    p[0] = p[1] = False
    i = 2
    while i * i <= n:
        if p[i]:
            for j in range(i * i, n + 1, i):
                p[j] = False
        i += 1
    return p
  • i*i がオーバーフローするなら long で比較
  • 0,1 は素数でない(初期化で false)
数学 gcd / lcm / extGcd ユークリッドの互除法 O(log N)

gcd は互除法。lcm は先に割って溢れ防止。extGcd は ax+by=gcd の (x,y) も求める(mod 逆元・不定方程式)。

gcd(a,b) = gcd(b, a%b),  gcd(a,0)=a
 gcd(12,18)=gcd(18,12)=gcd(12,6)=gcd(6,0)=6
lcm = a / gcd · b    (先に割る)
extGcd: ax + by = gcd の x,y も返す
from math import gcd                 # 標準で gcd / lcm(3.9+)
def lcm(a, b):
    return a // gcd(a, b) * b
def ext_gcd(a, b):                  # ax+by=gcd の (g, x, y)
    if b == 0:
        return a, 1, 0
    g, x, y = ext_gcd(b, a % b)
    return g, y, x - (a // b) * y
  • lcm は a*b が溢れる → a/gcd*b の順
  • 負数の gcd 符号に注意(必要なら abs)
動的計画法 ナップサック / 部分和 0-1 / 個数制限 DP O(NW)

容量ごとの最大価値。0-1 は重さを逆順ループ(各品物1回)。部分和は価値の代わりに可否を持つ。

品物(w,v), 容量cap. dp[w]=容量wの最大価値
for 品物: for w = cap .. wi  (逆順!):
   dp[w] = max(dp[w], dp[w-wi] + vi)
逆順=各品物1回。正順だと無制限個
部分和: dp[s] = s を作れるか (bool)
def knapsack01(w, v, cap):               # 各品物 1 個まで
    dp = [0] * (cap + 1)
    for wi, vi in zip(w, v):
        for j in range(cap, wi - 1, -1):    # 重さ逆順
            dp[j] = max(dp[j], dp[j - wi] + vi)
    return dp[cap]

def subset_sum(a, target):               # bitset で高速化
    dp = 1                                # s ビット目 = s を作れるか
    for x in a:
        dp |= dp << x
    return (dp >> target) & 1 == 1
  • 0-1 は必ず容量を逆順。正順にすると無制限ナップサックになる
  • 価値は溢れうる → Long で持つ
データ構造 セグメント木 点更新 + 区間クエリ O(log N)

非再帰・抽象化。op はモノイド(結合的 + 単位元 unit)。min/max/和などを区間で。

[5 3 7 1 9] を min セグ木に
         [1]            ← 全体 min
      [3]    [9]
   [3][7] [9][∞]
 [5][3][7][1][9]
update(i,v): 葉→根  query[l,r): 両端から畳む
class SegTree:
    # op はモノイド(結合的 + 単位元 unit). 例: min, max, 和
    def __init__(self, n, unit, op):
        self.unit, self.op = unit, op
        self.size = 1
        while self.size < n:
            self.size *= 2
        self.t = [unit] * (2 * self.size)
    def update(self, i, v):
        x = i + self.size
        self.t[x] = v
        x >>= 1
        while x:
            self.t[x] = self.op(self.t[2 * x], self.t[2 * x + 1])
            x >>= 1
    def query(self, l, r):                # [l, r)
        res = self.unit
        lo, hi = l + self.size, r + self.size
        while lo < hi:
            if lo & 1:
                res = self.op(res, self.t[lo]); lo += 1
            if hi & 1:
                hi -= 1; res = self.op(res, self.t[hi])
            lo >>= 1; hi >>= 1
        return res
  • query は半開 [l, r)
  • unit は演算の単位元 (min→∞, max→-∞, 和→0)
  • 区間更新が要るなら遅延セグ木に拡張
データ構造 座標圧縮 大きい値 → 0..k-1 O(N log N)

値の大小を保ったまま 0..k-1 に詰める。BIT/セグ木に乗せる前処理、値の種類数。

a    = [100  50 100   7]
sort & distinct = [7 50 100]  (→ 0 1 2)
comp = [  2   1   2   0]
逆引き: 圧縮値 i → vals[i] が元の値
def compress(a):
    # 値の大小を保ち 0..k-1 に圧縮。(圧縮後, 元の値) を返す
    vals = sorted(set(a))
    idx = {v: i for i, v in enumerate(vals)}
    return [idx[x] for x in a], vals
  • 重複は 1 つにまとめる(distinct)
  • 半開区間や境界を扱うなら +1 した値も入れることがある
グラフ Bellman-Ford 法 負辺ありの最短路 O(VE)

全辺を n-1 回緩和。負辺 OK。n 回目でも更新できれば負閉路。Dijkstra が使えない時に。

全辺を n-1 回 緩和(relax)
 dist[t] = min(dist[t], dist[f] + cost)
n 回目でも更新 → 負閉路あり
始点から到達する負閉路だけが検出対象
def bellman_ford(n, edges, s):
    # edges: list of (from, to, cost). 負閉路があれば None
    INF = float('inf')
    dist = [INF] * n; dist[s] = 0
    for _ in range(n - 1):
        for f, t, c in edges:
            if dist[f] != INF and dist[f] + c < dist[t]:
                dist[t] = dist[f] + c
    for f, t, c in edges:                  # n 回目で更新 → 負閉路
        if dist[f] != INF and dist[f] + c < dist[t]:
            return None
    return dist
  • dist[f] が INF の辺は緩和しない(INF + cost で誤更新)
  • 負閉路検出は n-1 回緩和の「後」にもう 1 周
グラフ Warshall-Floyd 法 全点対最短路 O(V³)

中継点 k を全部試す DP。V≤500 まで。負辺 OK(負閉路は dist[v][v]<0 で検出)。

中継点 k = 0..n-1 を全部試す
 dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])
隣接行列(辺なし=INF, 対角0)を渡し in-place 更新
ループ順は k, i, j の順 (k が最外)
def warshall_floyd(dist):
    # dist: 隣接行列(辺なし=inf, 対角0) を in-place 更新
    n = len(dist)
    INF = float('inf')
    for k in range(n):
        for i in range(n):
            if dist[i][k] == INF:
                continue
            dik = dist[i][k]
            row = dist[i]
            for j in range(n):
                if dik + dist[k][j] < row[j]:
                    row[j] = dik + dist[k][j]
  • ループ順は必ず k を最外に
  • INF 経由の誤更新を防ぐ(INF の行は skip)
グラフ トポロジカルソート DAG の順序付け (Kahn) O(V+E)

入次数 0 をキューから取り出し、辺を消しながら並べる。全頂点出せなければ閉路。

入次数0をキューへ → 取り出しつつ出る辺を消す
 (消した先の入次数が0になったら追加)
全頂点出れば順序確定 / 出きらねば閉路
辞書順最小が要るなら queue → 優先度付き
from collections import deque
def topo_sort(g):
    # g: 隣接リスト(有向). 閉路があれば None
    n = len(g)
    indeg = [0] * n
    for v in range(n):
        for to in g[v]:
            indeg[to] += 1
    q = deque(v for v in range(n) if indeg[v] == 0)
    order = []
    while q:
        v = q.popleft(); order.append(v)
        for to in g[v]:
            indeg[to] -= 1
            if indeg[to] == 0:
                q.append(to)
    return order if len(order) == n else None
  • 出力数 < N なら閉路あり
  • 辞書順最小は ArrayDeque を PriorityQueue に
グラフ Kruskal 法 (MST) 最小全域木 O(E log E)

辺を cost 昇順に見て、端点が別グループなら採用(Union-Find)。全部つなぐ最小コスト。

辺を cost 昇順にソート
 端点が別グループなら採用(UnionFind で併合)
 採用辺が n-1 本で全域木 完成
※ Union-Find のスニペットが必要
def kruskal(n, edges):
    # edges: list of (cost, u, v). UnionFind 必要。非連結なら None
    uf = UnionFind(n)
    total = used = 0
    for c, u, v in sorted(edges):
        if uf.union(u, v):
            total += c; used += 1
    return total if used == n - 1 else None
  • 採用辺が n-1 本に満たなければ非連結
  • 同コスト辺の順序は MST 重みに影響しない
ユーティリティ しゃくとり法 連続区間の最長/数え上げ O(N)

窓 [left,right] を右に伸ばし、条件を破ったら左を詰める。単調性が前提(非負配列など)。

[left,right] 窓を右へ伸ばし、破ったら左を詰める
 和<=k 最大長: 超えたら left++ で縮める
 和>=k 個数: 初めて満たせば右端以降は全部OK
単調性(伸ばすと悪化/縮めると改善)が必要
def longest_at_most(a, k):
    # 和が k 以下の連続区間の最大長 (a は非負)
    best = s = left = 0
    for right in range(len(a)):
        s += a[right]
        while s > k:
            s -= a[left]; left += 1
        best = max(best, right - left + 1)
    return best

def count_at_least(a, k):
    # 和が k 以上の連続区間の総数 (a は非負)
    n = len(a)
    count = s = right = 0
    for left in range(n):
        while right < n and s < k:
            s += a[right]; right += 1
        if s < k:
            break
        count += n - right + 1
        s -= a[left]
    return count
  • 負数があると単調性が崩れ使えない
  • right を左に戻さない(各ポインタは単調に進むだけ)
動的計画法 LIS / LCS / 編集距離 部分列 DP O(N log N) / O(NM)

LIS は末尾最小値を二分探索で更新。LCS・編集距離は 2 次元 DP 表。

LIS: tail[k] = 長さ k+1 の増加列の末尾の最小値
 各 x を lower_bound で 置換 or 追加 → 長さが答え
LCS/編集距離: dp[i][j] を表で
 一致なら \+1 / 不一致は周囲の最小から
from bisect import bisect_left
def lis(a):
    # 最長増加部分列 O(N log N)。広義単調増加なら bisect_right に
    tail = []
    for x in a:
        p = bisect_left(tail, x)
        if p == len(tail):
            tail.append(x)
        else:
            tail[p] = x
    return len(tail)

def lcs(s, t):                            # 最長共通部分列 O(NM)
    n, m = len(s), len(t)
    dp = [[0] * (m + 1) for _ in range(n + 1)]
    for i in range(n):
        for j in range(m):
            dp[i + 1][j + 1] = dp[i][j] + 1 if s[i] == t[j] \
                else max(dp[i][j + 1], dp[i + 1][j])
    return dp[n][m]

def edit_distance(s, t):                  # 編集距離 O(NM)
    n, m = len(s), len(t)
    dp = [[0] * (m + 1) for _ in range(n + 1)]
    for i in range(n + 1):
        dp[i][0] = i
    for j in range(m + 1):
        dp[0][j] = j
    for i in range(1, n + 1):
        for j in range(1, m + 1):
            c = 0 if s[i - 1] == t[j - 1] else 1
            dp[i][j] = min(dp[i - 1][j] + 1, dp[i][j - 1] + 1, dp[i - 1][j - 1] + c)
    return dp[n][m]
  • LIS 広義単調増加は lower→upper bound に変える
  • LCS/編集距離は O(NM) メモリ。長いと 1 次元ロールで節約
数学 素因数分解 / 約数 √N の整数論 O(√N)

p=2 から割り続ける素因数分解。約数は d と n/d をペアで集める。素数判定も同様。

factorize: p=2.. (p*p<=v) の間割り続ける
 残った v>1 は最大の素因数
 360 = 2^3 · 3^2 · 5
divisors: d*d<=n, n%d==0 で d と n/d を集める
 12 の約数 = 1 2 3 4 6 12
def factorize(n):                         # {素因数: 指数} O(√N)
    res = {}
    v, p = n, 2
    while p * p <= v:
        while v % p == 0:
            res[p] = res.get(p, 0) + 1
            v //= p
        p += 1
    if v > 1:
        res[v] = res.get(v, 0) + 1
    return res

def divisors(n):                          # 約数 (ソート済み) O(√N)
    small, large = [], []
    d = 1
    while d * d <= n:
        if n % d == 0:
            small.append(d)
            if d != n // d:
                large.append(n // d)
        d += 1
    return small + large[::-1]

def is_prime(n):
    if n < 2:
        return False
    d = 2
    while d * d <= n:
        if n % d == 0:
            return False
        d += 1
    return True
  • p*p<=v / d*d<=n で √N 打ち切り(オーバーフローは long)
  • クエリが多いなら篩で最小素因数表(spf)を作り O(log N) に
動的計画法 bitDP (TSP) 巡回セールスマン O(2ᴺN²)

訪問済み集合を bit で持つ DP。N≤16 程度。全頂点を回って戻る最小コスト等。

dp[S][v] = 訪問済み集合 S で今 v にいる最小コスト
 0 から出発: dp[{0}][0] = 0
 S に未訪問 to を足して遷移
最後に全訪問+0へ戻る最小。N<=16 (2^16·16^2)
def tsp(dist):
    # bitDP 巡回セールスマン O(2^N N^2). N<=16
    INF = float('inf')
    n = len(dist); full = 1 << n
    dp = [[INF] * n for _ in range(full)]
    dp[1][0] = 0
    for s in range(full):
        for v in range(n):
            if dp[s][v] == INF:
                continue
            for to in range(n):
                if s >> to & 1:
                    continue
                ns = s | (1 << to)
                cost = dp[s][v] + dist[v][to]
                if cost < dp[ns][to]:
                    dp[ns][to] = cost
    return min((dp[full - 1][v] + dist[v][0]
                for v in range(1, n) if dp[full - 1][v] != INF), default=INF)
  • 1 shl N の集合サイズ。N>20 で破綻
  • 到達不能 (INF) からは遷移しない
文字列 ローリングハッシュ 部分文字列比較 O(1) 構築 O(N) / 比較 O(1)

文字列を多項式ハッシュに。mod 2⁶¹-1 で衝突回避。部分文字列の一致判定が O(1)。

h[i] = s[0..i-1] の多項式ハッシュ (base 進数)
 get(l,r) = h[r] - h[l]·base^(r-l)  (mod 2^61-1)
部分文字列が等しい ⇔ ハッシュ一致 (O(1))
base はランダム、mod は 2^61-1 が安全
class RollingHash:
    # mod 2^61-1。Python は多倍長なので素直に書ける
    MOD = (1 << 61) - 1
    BASE = 1_000_003
    def __init__(self, s):
        n = len(s)
        self.h = [0] * (n + 1)
        self.pw = [1] * (n + 1)
        for i, ch in enumerate(s):
            self.h[i + 1] = (self.h[i] * self.BASE + ord(ch)) % self.MOD
            self.pw[i + 1] = self.pw[i] * self.BASE % self.MOD
    def get(self, l, r):                          # [l, r)
        return (self.h[r] - self.h[l] * self.pw[r - l]) % self.MOD
  • 単一ハッシュは衝突リスク。心配なら 2 種の mod で二重化
  • C++ は __int128、Java/Kotlin は Math.multiplyHigh で 128bit 乗算
幾何 平面幾何 ccw / 線分交差 / 凸包 凸包 O(N log N)

ccw(外積で回転方向)が基礎。線分交差・凸包・面積。誤差は EPS で比較、整数なら Long で。

ccw(a,b,c): 外積の符号で回転方向
  1:反時計 -1:時計 0/±2:一直線上
線分交差: 互いに相手を挟む ⇔ 交差
凸包(Andrew): x昇順→下側→上側
 cross<EPS で pop (左折だけ残す=反時計回り)
EPS = 1e-9
def sub(a, b): return (a[0] - b[0], a[1] - b[1])
def cross(a, b): return a[0] * b[1] - a[1] * b[0]
def dot(a, b): return a[0] * b[0] + a[1] * b[1]
def ccw(a, b, c):
    # 1:反時計 -1:時計 2:c-a-b -2:a-b-c 0:線分ab上
    ab, ac = sub(b, a), sub(c, a)
    cr = cross(ab, ac)
    if cr > EPS: return 1
    if cr < -EPS: return -1
    if dot(ab, ac) < -EPS: return 2
    if dot(ab, ab) < dot(ac, ac) - EPS: return -2
    return 0
def seg_intersect(a, b, c, d):
    return ccw(a, b, c) * ccw(a, b, d) <= 0 and ccw(c, d, a) * ccw(c, d, b) <= 0
def convex_hull(ps):                      # 反時計回り O(N log N)
    s = sorted(set(ps))
    if len(s) <= 2: return s
    h = []
    def build(floor, pts):
        for p in pts:
            while len(h) > floor and cross(sub(h[-1], h[-2]), sub(p, h[-1])) < EPS:
                h.pop()
            h.append(p)
    build(1, s); lower = len(h); build(lower, s[::-1][1:])
    return h[:-1]
def polygon_area(poly):                   # 符号付き面積(反時計回りで正)
    n = len(poly)
    return sum(cross(poly[i], poly[(i + 1) % n]) for i in range(n)) / 2
  • == でなく EPS 比較。退化(同一点・一直線)に注意
  • 整数座標なら Long の cross で誤差ゼロにできる
  • 凸包は一直線上の点を残すなら pop 条件を < -EPS に
グラフ 二部マッチング 増加路 (Hopcroft不要版) O(VE)

左頂点から増加路を DFS で探す。割り当て問題、最大マッチング = 最小頂点被覆(König)。

左→右の辺。各左頂点から増加路を DFS
 右が空 or その相手を押し出せれば マッチ確定
最大マッチング数 = 最小頂点被覆 (König の定理)
used[] を頂点ごとにリセットして探索
class BipartiteMatching:
    # 増加路 DFS O(VE)。左 n, 右 m
    def __init__(self, n, m):
        self.n, self.m = n, m
        self.g = [[] for _ in range(n)]
        self.match_r = [-1] * m
    def add_edge(self, u, v):
        self.g[u].append(v)
    def _dfs(self, u, used):
        for v in self.g[u]:
            if used[v]:
                continue
            used[v] = True
            if self.match_r[v] == -1 or self._dfs(self.match_r[v], used):
                self.match_r[v] = u
                return True
        return False
    def solve(self):
        res = 0
        for u in range(self.n):
            if self._dfs(u, [False] * self.m):
                res += 1
        return res
  • used は左頂点ごとに毎回リセット
  • もっと速くしたいなら Hopcroft-Karp / Dinic
グラフ Dinic 法 (最大流) 最大流 = 最小カット O(V²E)

BFS でレベル分けし、レベル順に DFS で流す。最大流・最小カット・二部マッチングに。

BFS でレベル(最短距離)を付ける
 → レベルが増える辺だけ DFS で流す
 逆辺(rev)に流量を戻し増加路を表現。繰り返す
最大流 = 最小カット。「同時不可の最小除去」に
from collections import deque
class Dinic:
    # 最大流 O(V^2 E)。各辺 [to, cap, rev]
    def __init__(self, n):
        self.n = n
        self.g = [[] for _ in range(n)]
    def add_edge(self, fr, to, cap):
        self.g[fr].append([to, cap, len(self.g[to])])
        self.g[to].append([fr, 0, len(self.g[fr]) - 1])
    def _bfs(self, s, t):
        self.level = [-1] * self.n
        self.level[s] = 0
        q = deque([s])
        while q:
            v = q.popleft()
            for to, cap, _ in self.g[v]:
                if cap > 0 and self.level[to] < 0:
                    self.level[to] = self.level[v] + 1
                    q.append(to)
        return self.level[t] >= 0
    def _dfs(self, v, t, f):
        if v == t:
            return f
        while self.it[v] < len(self.g[v]):
            e = self.g[v][self.it[v]]
            if e[1] > 0 and self.level[v] < self.level[e[0]]:
                d = self._dfs(e[0], t, min(f, e[1]))
                if d > 0:
                    e[1] -= d
                    self.g[e[0]][e[2]][1] += d
                    return d
            self.it[v] += 1
        return 0
    def max_flow(self, s, t):
        flow = 0
        while self._bfs(s, t):
            self.it = [0] * self.n
            while True:
                f = self._dfs(s, t, float('inf'))
                if f == 0:
                    break
                flow += f
        return flow
  • 容量は溢れない型(Long)。INF も大きすぎない値
  • iter[] で見た辺を再訪しない(これが効率の肝)