AIで解説 AtCoder攻略　関数グラフ・ダブリング

関数グラフ・ダブリングページの位置づけ

項目	内容
必修度	標準
学習目安	標準〜発展
前提	配列・二分累乗
対象問題	17問（推定値あり17問、未算出0問）

この記事のdifficulty区分は、問題を解く順番を決めるための目安です。AtCoderの公式なA〜F区分ではなく、取得できたdifficulty推定値を次の範囲に分けています。

学習目安	difficulty推定値	問題数
入門	difficulty < 0	1
標準	0〜799	3
標準〜発展	800〜1199	2
発展	1200以上	11
未算出	—	0

各頂点の次の行き先が一つだけ決まる関数グラフでは、遷移の繰り返しを倍々に前計算できます。周期と入口を分けると、巨大な回数の移動も対数時間で処理できます。

関数グラフの計算量を比べる

同じ遷移をK回たどるだけなら、1回ずつ進む方法はO(K)時間です。Kが10^18のように大きいと、入力Nが小さくても間に合いません。遷移を2^j回まとめて進む表を前計算すると、Kの二進表現に合わせて高々O(log K)回の表参照で済みます。表の作成にはO(N log K)時間とO(N log K)メモリを使うため、Kが大きい問題で候補になります。周期だけを求める問題なら、訪問済みを記録してO(N)で周期へ入る方法もあります。

問題ごとの細かな実装は異なりますが、最初に確認する条件は共通しています。

関数グラフ・ダブリングの見分け方

各状態から次の状態が一つだけある
K回後・周期・同じ頂点への合流を問われる
同じ遷移を何度もたどると計算量が大きい

関数グラフ・ダブリングの実装前チェック

遷移先を0始まりで保存する
2^j回後の遷移表を作る
周期に入る前の距離と周期長を分ける

先に確認する文法・ライブラリ

まずは必須Python文法で、入力・配列・条件分岐・ループなどの基本を確認してください。問題に合わせたキュー、ヒープ、二分探索などの選び方は標準ライブラリ・定石にまとめています。

代表問題で実装を確認する

最初の一問として、ABC228 B Takahashi’s Secret（公式解説）を解きます。各人が指す先を一度ずつたどり、同じ頂点に戻るまでに訪れた人数を数えます。遷移先が一つだけなので、隣接リストを作らず配列をそのまま追跡できます。

N, X = map(int, input().split())
X -= 1
A = [value - 1 for value in map(int, input().split())]

seen = [False] * N
answer = 0
while not seen[X]:
    seen[X] = True
    answer += 1
    X = A[X]

print(answer)

同じ頂点を二度処理しないため、計算量はO(N)、追加メモリもseen配列のO(N)です。

関数グラフ・ダブリングの学ぶ順番

このページでは全件を一度に並べず、difficultyの推定値を目安に代表問題を段階分けしています。難易度が未算出の問題は、制約と出題意図を先に確認します。

まず解く

問題	公式解説	出題意図	difficulty
ABC228 B Takahashi’s Secret	公式解説	各人が指す次の番号をたどり、0に到達するまでまたは再訪するまでの人数を数える。	-229
ABC337 C Lining Up 2	公式解説	Official editorial intent is classified as successor chain traversal.	225
ABC368 C Triple Attack	公式解説	Official editorial intent is classified as attack cycle.	367
ABC311 C Find it!	公式解説	Follow successor pointers from each node to find the directed cycle.	448
ABC228 D G. Linear Probing	公式解説	ハッシュ位置から次の空き位置をDSUの後継ポインタで求め、挿入後に次の空きへ連結する。	1035

次に解く

問題	公式解説	出題意図	difficulty
ABC179 E Sequence Sum	公式解説	x→x² mod Mの未出現判定で前周期と周期を分け、周期和をまとめてN項和を求める。	1175
ABC256 E H. Takahashi’s Anguish	公式解説	各頂点の出次数1グラフの各サイクルから最小コスト頂点を1つ選び、総和を求める。	1224
ABC241 E H. Putting Candies	公式解説	箱の遷移で現れる周期を検出し、周期前と周期内の累積和でK回後のキャンディ数を求める。	1248
ABC296 E H. Transition Game	公式解説	出次数1グラフでサイクルに属する頂点を葉削除により識別する。	1285
ABC357 E H. Reachability in Functional Graph	公式解説	Official editorial intent is classified as functional graph reach count.	1295

挑戦問題

問題	公式解説	出題意図	difficulty
ABC367 E H. Permute K times	公式解説	Official editorial intent is classified as functional graph binary lifting.	1370
ABC175 D Moving Piece	公式解説	置換を巡回路に分解し、各開始点の周回余りを列挙しつつ正の巡回和なら繰り返し分を加えて最大得点を求める。	1491
ABC377 E H. Permute K times 2	公式解説	置換の合成を二進累乗し、K回の同時更新後の写像を求める。	1685
ABC387 F I. Count Arrays	公式解説	関数グラフのサイクルと木を分解し、x_i≤x_Aiの値割当てをM段階DPで数える。	1760
ABC399 E H. Replace	公式解説	Model replacements as a function graph, reject conflicting outgoing mappings, and count vertices that eventually reach each cycle.	2045