問題
$N$ 頂点 $M$ 辺の有向グラフが与えられる。各頂点 $i$ から到達可能な頂点集合を、長さ $N$ の $01$ 文字列（$j$ 文字目が到達可能なら 1）で出力せよ（$i$ 自身も含む）。
制約
| パラメータ | 範囲 | 備考 |
|---|---|---|
| $N$ | $1 \le N \le 2000$ | 頂点数 |
| $M$ | $0 \le M \le N^2$ | 辺数 |
入出力例
入力例1
4 3
0 1
1 2
2 3出力例1
1111
0111
0011
0001概念図: 大整数の OR 演算で $N$ ビット分を一括処理
ヒント
ヒント1（方向性）
到達可能性を頂点対ごとに真偽値で Floyd-Warshall 型に計算すると $O(N^3)$ の真偽値演算が必要で $N=2000$ では遅い。各演算を64ビット単位でまとめられないか考える。
ヒント2（アプローチ）
各頂点の到達可能集合を巨大整数（ビットセット）で表現する。Python の任意精度整数は論理和 | を1回で全ビットまとめて計算できるため、内側演算 reach[i] |= reach[k] が実質 $O(N/64)$ 相当になる。
ヒント3（ほぼ答え）
reach = [1 << i for i in range(n)]
for u, v in edges:
reach[u] |= 1 << v
for k in range(n):
kb = 1 << k
for i in range(n):
if reach[i] & kb:
reach[i] |= reach[k]模範解答
import sys
def solve():
data = sys.stdin.read().split()
idx = 0
n = int(data[idx]); idx += 1
m = int(data[idx]); idx += 1
reach = [1 << i for i in range(n)]
for _ in range(m):
u = int(data[idx]); idx += 1
v = int(data[idx]); idx += 1
reach[u] |= 1 << v
for k in range(n):
kb = 1 << k
rk = reach[k]
for i in range(n):
if reach[i] & kb:
reach[i] |= rk
out = []
for i in range(n):
s = bin(reach[i])[2:].zfill(n)[::-1]
out.append(s)
print('\n'.join(out))
solve()計算量: 外側2重ループ $O(N^2)$ 回だが、各 |= が $O(N/64)$ ワード処理のため実質 $O(N^3/64)$ 相当。
Step-by-Step 解説
Step 1: ビットセットとしての初期化
各頂点 $i$ の到達可能集合を整数 reach[i] で表現し、自分自身のビットと直接の隣接辺を立てる。
Step 2: Warshall型DPの立式
頂点 $k$ を経由してよいときの到達可能性を $k=0,\dots,N-1$ の順に確定させる。$i$ から $k$ に到達できるなら $k$ の到達可能集合をまるごと $i$ に合成する。
Step 3: 整数単位で並列化
| 方式 | 1回の合成コスト |
|---|---|
| 真偽値ごとに更新 | $O(N)$（$N$回のbool演算） |
big int の |= | $O(N/64)$（ワード単位） |
Step 4: 出力形式への変換
bin() はビット0が文字列末尾に来るため zfill 後に [::-1] で反転し頂点番号順に対応させる。
よくあるミス
| ミス | 原因 | 正しい書き方 |
|---|---|---|
| 3重ループで真偽値ごとに更新 | ビットセットの利点を活かせず $O(N^3)$ | 内側は reach[i] |= reach[k] のみ |
reach[i] & kb の判定を忘れる | 到達できない場合でも情報を誤って取り込む | 到達可能性を確認してから合成 |
bin() の桁順序をそのまま出力 | ビット0が末尾に来るため逆順になる | zfill(n)[::-1] で反転 |
次のステップ
- 発展問題: 無向グラフの連結成分ビットセット高速化（Union-Findとの比較）
- 応用: LCS の bitset 高速化版（$O(NM/64)$）
自己評価
理解度: / /
自分の回答:
気づき・メモ: