分野別目次
初めてなら第1章の最初の単元から。 学びたい分野があれば、その章から読めます。 単元で考え方を学び、問題に取り組み、分からない前提へ戻って読み進めてください。
単元は読書順です。対象色は基本形を学ぶ目安で、問題の難易度や公式の履修基準とは別です。 直接の前提は各単元で確認できます。
第1章 モデル変換とアルゴリズム設計
問題文の操作を再利用可能な対象・不変量へ言い換え、探索・貪欲・分割手法を選ぶ共通の視点を最初に作る。
- 候補数を界して全列挙・有限case分解する緑色(800–1199)
- backtracking・可逆な探索状態緑色(800–1199)
- 同値な状態を正規化する水色(1200–1599)
- 疎なkeyの順序を保ってdense indexへ圧縮する緑色(800–1199)
- 局所寄与へ分解して集計順を交換する緑色(800–1199)
- 探索空間を分けて照合・再帰分割する水色(1200–1599)
- 再帰分割・分割統治水色(1200–1599)
- meet-in-the-middle・半分全列挙水色(1200–1599)
- 単調境界を証明して探索する緑色(800–1199)
- 尺取り法・sliding windowで連続区間を走査する緑色(800–1199)
- 交換論から選択順を導く水色(1200–1599)
- bitwise greedyによるmask最適化水色(1200–1599)
- 成立証明から構成解を復元する水色(1200–1599)
- 時間を逆向きにして未来依存を消す水色(1200–1599)
- event順にactive集合を更新する水色(1200–1599)
- 軽重分類と償却解析で総仕事量を抑える水色(1200–1599)
- 単調進行による償却解析水色(1200–1599)
- small-to-large・DSU on Tree青色(1600–1999)
- 平方根・閾値による軽重分類青色(1600–1999)
- parallel binary search・多数境界の判定共有青色(1600–1999)
- 基準witnessから変更影響を局所化する青色(1600–1999)
- 偶奇不変量からゲームの勝敗を決める青色(1600–1999)
- 対話protocolを守って情報を取得する緑色(800–1199)
- 情報量下界・query符号設計水色(1200–1599)
- 乱択の成功条件と誤り確率を設計する青色(1600–1999)
- 乱択代数fingerprint黄色(2000–2399)
- kinetic sorting・交差event順序更新橙色(2400–2799)
- XOR閾値matchingのbit分割再帰赤色(2800以上)
読書順の考え方・対象色の理由
まず全列挙と可逆な探索から正しい基準解を作り、正規化・座標圧縮・寄与分解で扱う対象を減らす。分割統治と半分全列挙で探索空間を分け、単調探索・尺取り・交換論で候補を捨てる理由を学ぶ。構成解の復元に続けて、逆順処理・event走査・償却解析・parallel binary search・変更影響の局所化まで汎用的な設計手法を学ぶ。その後にゲーム固有の偶奇不変量へ進み、対話と情報量、乱択と誤り評価を学んだ後、kineticな順序更新とXOR閾値matchingを複合的な発展として扱う。
導入対象の目安: 緑色(800–1199)。探索や集計を選ぶときに、答えに必要な条件と、計算を減らす根拠を言葉にするための入口です。
- 候補数を界して全列挙・有限case分解する — 緑色(800–1199)
制約から候補数を見積もり、成功までの探索回数を界する考え方を学ぶ。
- backtracking・可逆な探索状態 — 緑色(800–1199)
再帰と訪問済み管理を使い、選択と取り消しが対応する探索を実装する。
- 同値な状態を正規化する — 水色(1200–1599)
対称性で同じ候補をまとめ、代表だけを残してよい理由を示せるようにする。
- 疎なkeyの順序を保ってdense indexへ圧縮する — 緑色(800–1199)
整列と二分探索を使い、大小関係と実際の距離を区別して添字化する。
- 局所寄与へ分解して集計順を交換する — 緑色(800–1199)
要素・組・値・区間のどれを固定すれば一意に数えられるかを見抜き、総和の順を交換する。
- 探索空間を分けて照合・再帰分割する — 水色(1200–1599)
探索空間を独立に分ける場合と、再帰的な小問題へ分ける場合を区別する入口。
- 再帰分割・分割統治 — 水色(1200–1599)
分割・再帰・併合の役割を分け、重複のない合成と計算量を説明する。
概念上の親: 探索空間を分けて照合・再帰分割する
- meet-in-the-middle・半分全列挙 — 水色(1200–1599)
全列挙と整列・検索を組み合わせ、指数の半減と照合条件を設計する。
概念上の親: 探索空間を分けて照合・再帰分割する
- 単調境界を証明して探索する — 緑色(800–1199)
二分探索の実装に加え、判定の単調性と境界の意味を説明する。
- 尺取り法・sliding windowで連続区間を走査する — 緑色(800–1199)
窓の条件とpointerが戻らない理由を定め、全体の走査回数を数える。
- 交換論から選択順を導く — 水色(1200–1599)
選択の直感を交換論法や支配関係で裏付け、反例のある貪欲法を見分ける。
- bitwise greedyによるmask最適化 — 水色(1200–1599)
上位bitの優先性と単調な可否判定を組み合わせてmaskを決める。
- 成立証明から構成解を復元する — 水色(1200–1599)
存在判定の証明に操作列や親情報を対応させ、具体的な解へ戻す。
- 時間を逆向きにして未来依存を消す — 水色(1200–1599)
削除を追加に変えるなど、時間を逆に読むことで扱える操作を増やす。
- event順にactive集合を更新する — 水色(1200–1599)
時刻・座標で整列し、同時eventの順序とactive集合の不変量を保つ。
- 軽重分類と償却解析で総仕事量を抑える — 水色(1200–1599)
一操作の最悪時間から離れ、総仕事量と軽重分類で計算量を設計する入口。
- 単調進行による償却解析 — 水色(1200–1599)
一度だけの削除やpotentialの減少に課金し、操作列全体を評価する。
概念上の親: 軽重分類と償却解析で総仕事量を抑える
- small-to-large・DSU on Tree — 青色(1600–1999)
併合時の倍増と分割時の半減を使い、重複が消える場合も総走査量を証明する。
概念上の親: 軽重分類と償却解析で総仕事量を抑える
- 平方根・閾値による軽重分類 — 青色(1600–1999)
頻度や次数で場合分けし、二つの計算量の釣合いから閾値を選ぶ。
概念上の親: 軽重分類と償却解析で総仕事量を抑える
- parallel binary search・多数境界の判定共有 — 青色(1600–1999)
offline処理と二分探索を組み合わせ、複数queryで判定器の走査を共有する。
- 基準witnessから変更影響を局所化する — 青色(1600–1999)
基準解の実行可能性と最適性、または実行列の保存を証明し、答えが変わり得る変更だけを再計算する。
- 偶奇不変量からゲームの勝敗を決める — 青色(1600–1999)
局面ごとの勝敗再帰が不要な条件を見つけ、手数・終端量の偶奇から成立する戦略を証明する。
- 対話protocolを守って情報を取得する — 緑色(800–1199)
入出力手順・flush・問い合わせ上限を守り、単純な識別手順を実装する。
- 情報量下界・query符号設計 — 水色(1200–1599)
応答で区別できる状態数を数え、bit符号化と復号を設計する。
- 乱択の成功条件と誤り確率を設計する — 青色(1600–1999)
一回の成功確率と試行回数を結び付け、乱択が許す誤りを評価する。
- 乱択代数fingerprint — 黄色(2000–2399)
体やXORへの写像を設計し、代数的な衝突確率を全比較回数まで含めて評価する。
概念上の親: 乱択の成功条件と誤り確率を設計する
- kinetic sorting・交差event順序更新 — 橙色(2400–2799)
連続的な順序変化を隣接交差に限定し、失効eventと総event数を管理する。
- XOR閾値matchingのbit分割再帰 — 赤色(2800以上)
XOR閾値ごとにpair可能数を最大化するbit分割再帰を組み立て、同一部分集合内と二集合間のmatching数を合成する根拠を証明する。
第2章 データ構造と問い合わせ
問い合わせに必要な要約と更新規則を見抜く視点を先に学び、目的に合うデータ構造の選択へつなげる。
- 一次元・二次元累積和と差分で区間情報を線形化する茶色(400–799)
- 要素索引と連結リストで局所linkを更新する茶色(400–799)
- heap・ordered setで全候補の極値を保つ緑色(800–1199)
- priority queue・best-first列挙緑色(800–1199)
- ordered set・multisetの動的順序管理緑色(800–1199)
- 支配関係から不要な候補を単調stack・queueで削る水色(1200–1599)
- 大小関係をCartesian treeへ変換する青色(1600–1999)
- 反転数・重み付き接頭辞統計をFenwick Treeで保つ水色(1200–1599)
- 結合的な区間要約・区間分解・合成水色(1200–1599)
- 区間monoid要約水色(1200–1599)
- 区間更新を要約へ作用させる青色(1600–1999)
- 有限関数・作用の合成水色(1200–1599)
- 冪等演算のoverlap range query・Sparse Table水色(1200–1599)
- SWAG・two-stack queue aggregation青色(1600–1999)
- Segment Treeのcanonical区間分解青色(1600–1999)
- 静的sorted range index・Merge Sort Tree青色(1600–1999)
- 動的・implicit Segment Tree青色(1600–1999)
- 端点更新型のrun分割管理青色(1600–1999)
- 値軸のbucket分割と区間集約水色(1200–1599)
- Moの順序で区間問い合わせの差分を更新する青色(1600–1999)
- bitsetで集合演算をword並列化する水色(1200–1599)
- bit列をTrieで索引化する水色(1200–1599)
- 上位bitの支配関係によるXOR minimax青色(1600–1999)
- Rolling fingerprintで列の同値性を比較する水色(1200–1599)
- 列・文字列のrolling fingerprint水色(1200–1599)
- 構造を共有して過去の版を保存・復元する青色(1600–1999)
- rollback・DFS入退場の状態復元青色(1600–1999)
- 永続data structure・structural sharing黄色(2000–2399)
- Segment Tree Beats橙色(2400–2799)
読書順の考え方・対象色の理由
累積和・差分と局所link更新から始め、heap・ordered setと単調stackで候補を保つ。単調stackからCartesian treeを構築し、Fenwick TreeとSegment Treeの区間集約を学ぶ。monoid要約の直後にLazy Segment Treeの区間作用を置き、その後に関数合成・Sparse Table・SWAG・canonical decomposition・Merge Sort Tree・implicit Segment Treeを比較してから、run分割による動的区間管理を扱う。bucketとMo、bit列とfingerprintを用途別に比較した後、過去の版と条件付き更新へ進む。最後のSegment Tree Beatsでは遅延作用と償却解析を組み合わせる。
導入対象の目安: 緑色(800–1199)。必要な操作と保持する情報を整理し、基本コンテナから区間構造へ進む入口。
- 一次元・二次元累積和と差分で区間情報を線形化する — 茶色(400–799)
加算と差分で区間を表し、一次元から二次元の包除へ広げる。
- 要素索引と連結リストで局所linkを更新する — 茶色(400–799)
配列や辞書で要素を索引化し、挿入・削除で変わる前後関係だけを更新する。
- heap・ordered setで全候補の極値を保つ — 緑色(800–1199)
極値の取得と近傍の検索を区別し、heapとordered setを使い分ける入口。
- priority queue・best-first列挙 — 緑色(800–1199)
優先度付きキューで、現在選べる候補だけを管理して順に取り出す。
概念上の親: heap・ordered setで全候補の極値を保つ
- ordered set・multisetの動的順序管理 — 緑色(800–1199)
前後要素・重複を管理し、二集合に分けて境界と集計値を保つ基本操作を学ぶ。
概念上の親: heap・ordered setで全候補の極値を保つ
- 支配関係から不要な候補を単調stack・queueで削る — 水色(1200–1599)
将来不要な候補を削る支配関係と、一要素一度の償却計算量を説明する。
- 大小関係をCartesian treeへ変換する — 青色(1600–1999)
単調stackから木を構築し、区間極値と再帰分割が同じ構造になることを使う。
- 反転数・重み付き接頭辞統計をFenwick Treeで保つ — 水色(1200–1599)
座標圧縮と動的prefix和を組み合わせ、反転数や重み付き統計を数える。
- 結合的な区間要約・区間分解・合成 — 水色(1200–1599)
結合則・単位元・順序を区間集約の共通言語として使う入口。
- 区間monoid要約 — 水色(1200–1599)
十分な要約と結合演算を定義し、Segment Treeへ正しく載せる。
概念上の親: 結合的な区間要約・区間分解・合成
- 区間更新を要約へ作用させる — 青色(1600–1999)
要約に対する作用と作用同士の合成を定義し、遅延評価の整合性を説明する。
- 有限関数・作用の合成 — 水色(1200–1599)
小さな遷移表を関数として合成し、適用順の逆転を避ける。
概念上の親: 結合的な区間要約・区間分解・合成
- 冪等演算のoverlap range query・Sparse Table — 水色(1200–1599)
冪等性が区間の重複を許す理由を理解し、静的queryをSparse Tableで処理する。
概念上の親: 結合的な区間要約・区間分解・合成
- SWAG・two-stack queue aggregation — 青色(1600–1999)
非可換な結合順を二つのstackで保ち、窓の集約を償却定数時間にする。
概念上の親: 結合的な区間要約・区間分解・合成
- Segment Treeのcanonical区間分解 — 青色(1600–1999)
区間を少数のnodeへ分解する性質を、値の集約以外の配置にも使う。
概念上の親: 結合的な区間要約・区間分解・合成
- 静的sorted range index・Merge Sort Tree — 青色(1600–1999)
区間分解・整列列・prefix和を組み合わせ、二つの軸を持つ問い合わせを処理する。
概念上の親: Segment Treeのcanonical区間分解
- 動的・implicit Segment Tree — 青色(1600–1999)
通常のSegment Treeを疎なnode生成へ拡張し、座標域とnode数を別々に評価する。
概念上の親: 結合的な区間要約・区間分解・合成
- 端点更新型のrun分割管理 — 青色(1600–1999)
run分割やactive区間の和集合を管理し、endpoint更新・重複被覆・消去回数の償却を説明する。
- 値軸のbucket分割と区間集約 — 水色(1200–1599)
平方根分割で完全blockと端数を分け、更新とqueryの費用を調整する。
- Moの順序で区間問い合わせの差分を更新する — 青色(1600–1999)
追加・削除可能な集計を作り、query順の変更で端点移動量を抑える。
- bitsetで集合演算をword並列化する — 水色(1200–1599)
真偽配列の演算をbit演算へ写し、word幅を含めた計算量を見積もる。
- bit列をTrieで索引化する — 水色(1200–1599)
整数の大小とXORを上位bitからの分岐に写して検索する。
- 上位bitの支配関係によるXOR minimax — 青色(1600–1999)
上位bitが最大値を支配することを使い、二群への再帰とminimaxを導く。
- Rolling fingerprintで列の同値性を比較する — 水色(1200–1599)
列の一致判定を連結可能な要約へ写し、衝突のある比較として扱う入口。
- 列・文字列のrolling fingerprint — 水色(1200–1599)
prefix hashと連結則を実装し、長さ・指数位置・衝突確率を確認する。
- 構造を共有して過去の版を保存・復元する — 青色(1600–1999)
過去へ戻す操作と過去の版を残す操作の違いを理解する入口。
- rollback・DFS入退場の状態復元 — 青色(1600–1999)
変更前の差分を保存し、DFSや時間分割から戻るたびに不変量を復元する。
概念上の親: 構造を共有して過去の版を保存・復元する
- 永続data structure・structural sharing — 黄色(2000–2399)
更新pathだけの複製と共有部分の不変性を理解し、複数versionを管理する。
概念上の親: 構造を共有して過去の版を保存・復元する
- Segment Tree Beats — 橙色(2400–2799)
一括更新が失敗する条件を要約に持たせ、再帰下降の回数まで償却解析する。
第3章 動的計画法
状態と遷移の設計を共通言語にし、集合・列・確率・ゲーム・遷移高速化へ進む土台を作る。
- 最小十分状態からDPを設計する緑色(800–1199)
- グリッド・多次元表の局所DPを設計する緑色(800–1199)
- 資源・容量DP緑色(800–1199)
- 列・編集距離・区間合成DP緑色(800–1199)
- 列・subsequence DP緑色(800–1199)
- LIS・末尾の支配関係水色(1200–1599)
- 値域集約による部分列DP水色(1200–1599)
- prefix分割DP水色(1200–1599)
- 区間合成・領域分割DP水色(1200–1599)
- 区間拡張DP青色(1600–1999)
- 部分集合・bitmask状態DP水色(1200–1599)
- 接頭辞から更新する有限状態DP水色(1200–1599)
- 上限制約付き桁DP水色(1200–1599)
- automaton上のDP・行列遷移青色(1600–1999)
- 繰り上がり・借り・混合基数を状態にするDP青色(1600–1999)
- 確率過程・期待値DP水色(1200–1599)
- ゲーム状態の勝敗とGrundy数水色(1200–1599)
- minimax・得点差・局面値を評価するゲームDP水色(1200–1599)
- DP遷移を因数分解・集約して加速する青色(1600–1999)
- 固定線形遷移を巨大回数進める青色(1600–1999)
- 循環局面の後退解析とminimax距離黄色(2000–2399)
- frontier/profile DP・境界状態圧縮黄色(2000–2399)
- Steiner tree subset DP橙色(2400–2799)
- 大容量unbounded knapsackのeventual linearity橙色(2400–2799)
- 期待値の頻度圧縮と加法的ポテンシャル橙色(2400–2799)
- 独立な数ゲームの和赤色(2800以上)
読書順の考え方・対象色の理由
最小十分状態を定め、グリッド・容量・列・prefix分割・区間・部分集合という基本的な依存構造を比較する。桁上限・automaton・carryによる有限状態化まで一巡した後、確率とゲームで遷移の評価方法を変える。基本的なDP類型を学んでから遷移最適化と固定線形遷移の累乗へ進み、循環局面の後退解析へ広げる。後半は境界圧縮、Steiner木、巨大容量、期待値の状態削減、数ゲームの和を発展として扱う。列DPのLISと値域集約を比較し、automatonは文字列章、Steiner木は最短路の単元を先に参照する。
導入対象の目安: 緑色(800–1199)。状態・基底・遷移・計算順を明示する習慣を身につける入口。
- 最小十分状態からDPを設計する — 緑色(800–1199)
未来の選択に必要な情報だけを残し、履歴を同じ状態へまとめる。
- グリッド・多次元表の局所DPを設計する — 緑色(800–1199)
二次元以上の添字と依存順を定め、隣接状態から表を埋める。
- 資源・容量DP — 緑色(800–1199)
個数・容量を軸とするナップサック型DPを実装し、更新方向を説明する。
- 列・編集距離・区間合成DP — 緑色(800–1199)
prefix・最後の要素・区間という状態の違いを見渡す入口。
- 列・subsequence DP — 緑色(800–1199)
選ぶ・選ばない遷移と最後の要素を状態にし、同じ要素の重複利用を避ける。
概念上の親: 列・編集距離・区間合成DP
- LIS・末尾の支配関係 — 水色(1200–1599)
末尾の支配関係で状態を圧縮し、二分探索の境界と復元方法を理解する。
概念上の親: 列・subsequence DP
- 値域集約による部分列DP — 水色(1200–1599)
列DPの遷移を値域の集約へ写し、Segment Treeと更新順を組み合わせる。
概念上の親: 列・subsequence DP
- prefix分割DP — 水色(1200–1599)
最後の切れ目を固定し、漏れと重複のない分割の漸化式を立てる。
概念上の親: 列・編集距離・区間合成DP
- 区間合成・領域分割DP — 水色(1200–1599)
小区間の独立性と長さ順の依存を確認し、分割点を遷移にする。
概念上の親: 列・編集距離・区間合成DP
- 区間拡張DP — 青色(1600–1999)
訪問済み範囲と現在の端で履歴を圧縮し、移動が往復しても非循環なDPを作る。
概念上の親: 列・編集距離・区間合成DP
- 部分集合・bitmask状態DP — 水色(1200–1599)
使用集合をbitmaskで持ち、集合の増減と遷移順から指数時間DPを設計する。
- 接頭辞から更新する有限状態DP — 水色(1200–1599)
prefixの有限情報だけを持つDPを、桁の上限や文字列の制約へ使う入口。
- 上限制約付き桁DP — 水色(1200–1599)
tight・先頭の0・残す統計を分け、上限以下の整数を重複なく数える。
概念上の親: 接頭辞から更新する有限状態DP
- automaton上のDP・行列遷移 — 青色(1600–1999)
構成済みautomatonと位置の直積を使い、禁止状態と受理状態を区別して数える。
概念上の親: 接頭辞から更新する有限状態DP
- 繰り上がり・借り・混合基数を状態にするDP — 青色(1600–1999)
繰り上がりや借りだけを次の桁へ渡し、通常の桁DPと異なる走査方向を設計する。
- 確率過程・期待値DP — 水色(1200–1599)
一段先で条件分けし、確率・期待値の式と自己ループの移項を扱う。
- ゲーム状態の勝敗とGrundy数 — 水色(1200–1599)
DAG上の勝敗再帰からGrundy数へ進み、独立なゲームの和をXORで評価する。
- minimax・得点差・局面値を評価するゲームDP — 水色(1200–1599)
手番と終端利得を明示し、minimaxや得点差の再帰を実装する。
- DP遷移を因数分解・集約して加速する — 青色(1600–1999)
漸化式の共通項・例外・集約範囲を取り出し、状態数と遷移数を別々に減らす。
- 固定線形遷移を巨大回数進める — 青色(1600–1999)
固定線形遷移を行列や漸化式へ写し、巨大回数の反復を二分累乗する。
- 循環局面の後退解析とminimax距離 — 黄色(2000–2399)
循環する局面でOR・ANDの確定条件を分け、引き分けと有限minimax距離を判定する。
- frontier/profile DP・境界状態圧縮 — 黄色(2000–2399)
境界から離れた情報を忘れ、接続関係を正規化した幅指数の状態を設計する。
- Steiner tree subset DP — 橙色(2400–2799)
terminal集合の分割と多始点最短路を交互に使い、部分解の合成を正当化する。
- 大容量unbounded knapsackのeventual linearity — 橙色(2400–2799)
交換論で例外部分を有限に界し、巨大容量を小さなDPと線形部分へ分ける。
- 期待値の頻度圧縮と加法的ポテンシャル — 橙色(2400–2799)
対称性と線形性で期待値を頻度別関数の和に分離し、終端条件まで較正する。
- 独立な数ゲームの和 — 赤色(2800以上)
partisan gameが数になる条件と数の独立和を理解し、Grundy数との違いを扱う。
第4章 グラフアルゴリズム
対象を頂点と辺へ写して到達可能性を扱えるようにし、連結性・最短路・木・フローへ進む土台を作る。
- 状態グラフ探索・到達関係緑色(800–1199)
- 状態グラフのモデリングと探索緑色(800–1199)
- 推移閉包水色(1200–1599)
- 方向別grid scanによる長距離効果の前計算水色(1200–1599)
- 二部彩色と成分構造を扱う緑色(800–1199)
- 連結成分を管理し縮約する緑色(800–1199)
- DSUによる連結成分管理・縮約緑色(800–1199)
- 静的graph等式制約のpotential伝播水色(1200–1599)
- potential・weighted DSU青色(1600–1999)
- 重み付き最短路・経路復元・差分制約緑色(800–1199)
- 最短路モデル緑色(800–1199)
- 最短路を証明する木・経路の復元水色(1200–1599)
- difference constraints・不等式系の最短路化青色(1600–1999)
- SCCで閉路・DAG順・2-SATを処理する水色(1200–1599)
- DAGのtopological processing緑色(800–1199)
- 有向cycle検出・sink/source peeling水色(1200–1599)
- SCC・縮約DAG・トポロジカル順序水色(1200–1599)
- 2-SAT・含意グラフ青色(1600–1999)
- 一意な後続・サイクル・ダブリング水色(1200–1599)
- 関数グラフのcycle・tree分解水色(1200–1599)
- doubling・binary lifting水色(1200–1599)
- cut・cycle性質から最適全域木を構成する水色(1200–1599)
- Kruskal順の閾値DSU sweep青色(1600–1999)
- lowlinkで橋・関節点を特定する青色(1600–1999)
- 次数parityからwalkや選択辺集合を判定・構成する水色(1200–1599)
- Euler trail・circuit水色(1200–1599)
- 指定次数parityの部分グラフ構成青色(1600–1999)
- フロー・マッチング・カットへ帰着する青色(1600–1999)
- 二部matching・Hall・Kőnig青色(1600–1999)
- 最大流・最小カット青色(1600–1999)
- 閉路数・次数構造からgraph coreを調べる水色(1200–1599)
- 単一サイクル成分とgraph core水色(1200–1599)
- cycle space・fundamental cycle basis青色(1600–1999)
- 単調path contraction・DSU jump青色(1600–1999)
- near-tree graphのkernel化黄色(2000–2399)
- 有向walkの周期・cycle差分gcd黄色(2000–2399)
- 下限制約付きflowの実現可能性黄色(2000–2399)
- 最小費用流・circulation黄色(2000–2399)
- 重み付き二部完全matching黄色(2000–2399)
- 平面graph双対・cut/path対応黄色(2000–2399)
- path matchingのheap縮約greedy橙色(2400–2799)
- 一般グラフの最小重み完全matching赤色(2800以上)
読書順の考え方・対象色の理由
graph search・状態グラフ・推移閉包の後に方向別grid scanを置き、探索と局所的な状態伝播を続けて学ぶ。二部構造・連結性・最短路・有向構造・関数グラフ・全域木・lowlinkで標準的なgraph toolkitを揃える。Euler trailの次数条件と偶奇部分グラフの後に、二部matching・max-flow/min-cutへの標準的な帰着を学ぶ。続いてgraph core・cycle spaceを扱い、単調path縮約・near-tree kernel化・有向walk周期へ進む。lower-bound flow・min-cost flow・weighted bipartite matchingは発展的なflowとして後半に置き、planar duality・path matching contraction・一般重み付きmatchingで締めくくる。
導入対象の目安: 緑色(800–1199)。状態と遷移を頂点と辺で表し、距離・連結性・向きの違いを整理する入口。
- 状態グラフ探索・到達関係 — 緑色(800–1199)
入力の頂点以外にも状態を作り、探索と到達関係を使う入口。
- 状態グラフのモデリングと探索 — 緑色(800–1199)
位置と補助情報を一つの頂点にし、状態数・辺数を見積もってBFSやDFSを使う。
概念上の親: 状態グラフ探索・到達関係
- 推移閉包 — 水色(1200–1599)
到達関係の推移性を行列更新やbitsetでまとめて計算する。
概念上の親: 状態グラフ探索・到達関係
- 方向別grid scanによる長距離効果の前計算 — 水色(1200–1599)
方向ごとの走査で長距離の影響を前計算し、探索中の判定を軽くする。
概念上の親: 状態グラフ探索・到達関係
- 二部彩色と成分構造を扱う — 緑色(800–1199)
二部性と部の反転対称性を扱い、連結二部グラフの彩色重複も補正する。
- 連結成分を管理し縮約する — 緑色(800–1199)
連結成分を単位に情報を管理し、探索と成分併合を使い分ける入口。
- DSUによる連結成分管理・縮約 — 緑色(800–1199)
代表と成分サイズを管理し、辺追加による連結性をDSUで処理する。
概念上の親: 連結成分を管理し縮約する
- 静的graph等式制約のpotential伝播 — 水色(1200–1599)
辺の差やXORを伝播し、閉路の整合性と成分ごとの自由度を確認する。
概念上の親: 連結成分を管理し縮約する
- potential・weighted DSU — 青色(1600–1999)
DSUの親への差を保ち、経路圧縮・併合時の符号と矛盾判定を導く。
概念上の親: 連結成分を管理し縮約する
- 重み付き最短路・経路復元・差分制約 — 緑色(800–1199)
辺の重みに合う距離計算を選び、最短路の復元へ進む入口。
- 最短路モデル — 緑色(800–1199)
重みと状態の定義を確認し、Dijkstraなどの標準的な最短路算法を使い分ける。
概念上の親: 重み付き最短路・経路復元・差分制約
- 最短路を証明する木・経路の復元 — 水色(1200–1599)
距離だけでなく到達元を保持し、最短路条件を満たす木や経路を取り出す。
概念上の親: 重み付き最短路・経路復元・差分制約
- difference constraints・不等式系の最短路化 — 青色(1600–1999)
不等式を辺へ変換し、負閉路と可解性・最適なpotentialの関係を説明する。
概念上の親: 重み付き最短路・経路復元・差分制約
- SCCで閉路・DAG順・2-SATを処理する — 水色(1200–1599)
有向グラフの循環部分と非循環部分を区別し、縮約して処理する入口。
- DAGのtopological processing — 緑色(800–1199)
入次数による処理順を作り、有向非循環グラフ上の伝播やDPを実装する。
概念上の親: SCCで閉路・DAG順・2-SATを処理する
- 有向cycle検出・sink/source peeling — 水色(1200–1599)
DFSの訪問状態や次数零の反復削除から、有向cycleと残る領域を判定する。
概念上の親: SCCで閉路・DAG順・2-SATを処理する
- SCC・縮約DAG・トポロジカル順序 — 水色(1200–1599)
相互到達性で頂点をまとめ、縮約後がDAGになることを使う。
概念上の親: SCCで閉路・DAG順・2-SATを処理する
- 2-SAT・含意グラフ — 青色(1600–1999)
二値制約を含意へ変換し、literalと否定のSCCから可解性と代入を得る。
概念上の親: SCCで閉路・DAG順・2-SATを処理する
- 一意な後続・サイクル・ダブリング — 水色(1200–1599)
後続が一意な遷移をcycleと流入木に分け、反復を圧縮する入口。
- 関数グラフのcycle・tree分解 — 水色(1200–1599)
前周期と周期を分離し、cycleへの流入と巨大回数の移動を扱う。
概念上の親: 一意な後続・サイクル・ダブリング
- doubling・binary lifting — 水色(1200–1599)
二の冪回の遷移を合成し、行き先や累積値を対数回で求める。
概念上の親: 一意な後続・サイクル・ダブリング
- cut・cycle性質から最適全域木を構成する — 水色(1200–1599)
DSUやheapを用い、cut・cycle性質で全域木の辺選択を正当化する。
- Kruskal順の閾値DSU sweep — 青色(1600–1999)
辺とqueryを同じ重み順に処理し、連結する閾値と同重みの扱いを整理する。
概念上の親: cut・cycle性質から最適全域木を構成する
- lowlinkで橋・関節点を特定する — 青色(1600–1999)
DFS木と後退辺を区別し、lowlinkの不変量から橋・関節点を判定する。
- 次数parityからwalkや選択辺集合を判定・構成する — 水色(1200–1599)
次数と連結性から全辺を使う歩道や選択辺集合の条件を読む入口。
- Euler trail・circuit — 水色(1200–1599)
次数条件を理解し、辺を一度ずつ使うHierholzer法を実装する。
概念上の親: 次数parityからwalkや選択辺集合を判定・構成する
- 指定次数parityの部分グラフ構成 — 青色(1600–1999)
木の葉から奇偶条件を確定し、指定した奇数次数集合を実現する。
概念上の親: 次数parityからwalkや選択辺集合を判定・構成する
- フロー・マッチング・カットへ帰着する — 青色(1600–1999)
割当て・容量・cutの制約を読み、matchingとflowへの還元を選ぶ入口。
- 二部matching・Hall・Kőnig — 青色(1600–1999)
増加路を理解し、Hall条件と最小頂点被覆を割当て問題へ使う。
概念上の親: フロー・マッチング・カットへ帰着する
- 最大流・最小カット — 青色(1600–1999)
残余グラフとcutの意味を理解し、選択・排反を容量networkへ還元する。
概念上の親: フロー・マッチング・カットへ帰着する
- 閉路数・次数構造からgraph coreを調べる — 水色(1200–1599)
辺数と頂点数から閉路数を読み、次数条件で残る核を取り出す入口。
- 単一サイクル成分とgraph core — 水色(1200–1599)
成分のE−V+1から閉路数を読み、必要なら葉を剥がして残るcoreを調べる。
概念上の親: 閉路数・次数構造からgraph coreを調べる
- cycle space・fundamental cycle basis — 青色(1600–1999)
非木辺と基本cycleを対応させ、偶数次数の辺集合をF₂上の基底で表し、辺ラベルによるcycle空間の線形像をXOR spanへ移す。
- 単調path contraction・DSU jump — 青色(1600–1999)
確定した区間を次未処理pointerで飛ばし、削除済み部分を再走査しない。
- near-tree graphのkernel化 — 黄色(2000–2399)
葉と次数2のchainを答えを保って縮約し、余分な辺数で残るサイズを界する。
- 有向walkの周期・cycle差分gcd — 黄色(2000–2399)
SCC内の閉路長を差分のgcdでまとめ、巨大歩数の到達条件を周期へ写す。
- 下限制約付きflowの実現可能性 — 黄色(2000–2399)
下限を需要へ移し、補助source・sinkでcirculationの可解性を判定する。
概念上の親: フロー・マッチング・カットへ帰着する
- 最小費用流・circulation — 黄色(2000–2399)
残余辺の費用とpotentialを理解し、流量別の最小費用へ還元する。
概念上の親: フロー・マッチング・カットへ帰着する
- 重み付き二部完全matching — 黄色(2000–2399)
assignmentの双対potentialとtight edgeを理解し、Hungarian法や費用流を選ぶ。
概念上の親: フロー・マッチング・カットへ帰着する
- 平面graph双対・cut/path対応 — 黄色(2000–2399)
平面埋め込みのfaceを構成し、primalのcutとdualのpath・cycleを対応させる。
- path matchingのheap縮約greedy — 橙色(2400–2799)
選んだ辺の近傍を補正して縮約し、各cardinalityの最適値が得られる理由を示す。
- 一般グラフの最小重み完全matching — 赤色(2800以上)
奇cycleのblossom縮約またはTutte多項式を使う一般matchingの理論を学ぶ。
第5章 木構造
一般グラフから独立させ、根・部分木・一意path・separatorという木固有の不変量を体系的に積み上げる。
- 基準点からの木距離・剰余類・直径・中心水色(1200–1599)
- 木DP・集約・rerooting水色(1200–1599)
- 根付き木DP・部分木集約水色(1200–1599)
- rerooting・全方位木DP青色(1600–1999)
- 木のancestor・部分木・pathを索引化する水色(1200–1599)
- Euler順による部分木区間化水色(1200–1599)
- ancestor query・LCA水色(1200–1599)
- Heavy-Light Decomposition青色(1600–1999)
- virtual tree・auxiliary tree黄色(2000–2399)
- 対称性・深さ・label区間で巨大な完全二分木を数える水色(1200–1599)
- laminar区間族の包含木構築青色(1600–1999)
- DSU merge tree・Kruskal reconstruction tree青色(1600–1999)
- 木の均衡分離点から重心分解へ進む黄色(2000–2399)
- 加法的tree metric復元橙色(2400–2799)
- 01 on Tree・親先行順序のcluster縮約橙色(2400–2799)
- heavy path上の多項式木DP橙色(2400–2799)
- rake・compressで動的木DPを保つ橙色(2400–2799)
- 資源DPを引数で渡すHLRecDP赤色(2800以上)
読書順の考え方・対象色の理由
一意な経路と距離・直径を確認し、根付き木DP・rerootingで部分木と全方位集約を学ぶ。Euler順・LCA・HLD・virtual treeで部分木・祖先・pathを扱う一般的なtoolkitを揃えた後、暗黙の完全二分木を展開せずに数える。続いて包含関係や併合履歴を木にする方法、重心分解、距離からの木の復元、親先行順序の縮約へ進む。後半は多項式木DP、rake・compressによる動的木DP、資源DPを渡すHLRecDPを扱う。多項式木DPでは代数章の畳み込みを先に学ぶ。
導入対象の目安: 水色(1200–1599)。探索で得る木の距離・祖先・部分木を、集約と分解の共通の土台にする入口。
- 基準点からの木距離・剰余類・直径・中心 — 水色(1200–1599)
一意経路と直径端点の性質を理解し、少数の距離計算で全頂点を評価する。
- 木DP・集約・rerooting — 水色(1200–1599)
部分木から親へ渡す要約を定め、根の移動やpath上の合成へ進む入口。
- 根付き木DP・部分木集約 — 水色(1200–1599)
子部分木の独立性と親へ渡す状態を定め、bottom-upに合成する。
概念上の親: 木DP・集約・rerooting
- rerooting・全方位木DP — 青色(1600–1999)
各辺の両側の情報を設計し、prefix・suffix合成で全根の答えを求める。
概念上の親: 木DP・集約・rerooting
- 木のancestor・部分木・pathを索引化する — 水色(1200–1599)
木を区間や祖先関係へ写し、配列上の算法へ接続する入口。
- Euler順による部分木区間化 — 水色(1200–1599)
DFS時刻で部分木が連続区間になることを使い、区間queryへ写す。
概念上の親: 木のancestor・部分木・pathを索引化する
- ancestor query・LCA — 水色(1200–1599)
深さ調整とbinary liftingを用い、LCA・祖先・距離のqueryを処理する。
概念上の親: 木のancestor・部分木・pathを索引化する
- Heavy-Light Decomposition — 青色(1600–1999)
軽い辺の回数を界し、pathを少数の区間に分解して順序付きqueryを処理する。
概念上の親: 木のancestor・部分木・pathを索引化する
- virtual tree・auxiliary tree — 黄色(2000–2399)
Euler順と隣接LCAで必要な分岐点だけを残し、小さな木上で計算する。
概念上の親: 木のancestor・部分木・pathを索引化する
- 対称性・深さ・label区間で巨大な完全二分木を数える — 水色(1200–1599)
二冪・深さ・heap番号の区間を使い、巨大な完全二分木を展開せず数える。
- laminar区間族の包含木構築 — 青色(1600–1999)
包含条件を確認し、端点の整列とstackで直接の親を構築する。
- DSU merge tree・Kruskal reconstruction tree — 青色(1600–1999)
DSUの併合履歴を木に保存し、時刻や閾値のqueryを祖先関係へ写す。
- 木の均衡分離点から重心分解へ進む — 黄色(2000–2399)
重み付きの一点分離と、頂点数を半減させる再帰分解を区別し、分離点を通る寄与を集計する。
- 加法的tree metric復元 — 橙色(2400–2799)
距離行列から接続先と辺長を復元し、加法性と全距離の整合を検証する。
- 01 on Tree・親先行順序のcluster縮約 — 橙色(2400–2799)
親先行制約の交換比較量を導き、clusterをheapとDSUで縮約する。
- heavy path上の多項式木DP — 橙色(2400–2799)
多項式の木DPをheavy path上の合成にまとめ、軽い部分木の総費用を評価する。
- rake・compressで動的木DPを保つ — 橙色(2400–2799)
境界付きclusterのrake・compressを設計し、更新の影響を木DPの合成で伝播する。
- 資源DPを引数で渡すHLRecDP — 赤色(2800以上)
資源DPを再帰の引数にし、軽い子への重複呼出しまで含めて計算量を証明する。
第6章 文字列アルゴリズム
接頭辞・接尾辞・一致長などの文字列状態を共通言語にし、各種の照合・索引法へ進む土台を作る。
- Trieで共有接頭辞を索引化する水色(1200–1599)
- 接頭辞との一致長を再利用する水色(1200–1599)
- Z algorithmによるprefix matching水色(1200–1599)
- 文字列周期・primitive word青色(1600–1999)
- 回文半径と左右対称区間を特定する青色(1600–1999)
- 接尾辞の順序とLCPを索引化する青色(1600–1999)
- 禁止・要求patternを有限状態へ圧縮する青色(1600–1999)
- 有限状態automatonの構成青色(1600–1999)
- Aho–Corasick黄色(2000–2399)
- 非決定性automatonのsubset construction黄色(2000–2399)
- Suffix Automatonで部分文字列集合を表す橙色(2400–2799)
- run-length状態の動的遷移青色(1600–1999)
- 圧縮・反復・再帰文字列へ問い合わせる青色(1600–1999)
読書順の考え方・対象色の理由
Trieによる接頭辞共有とprefix matching・Z algorithmによる一致区間の再利用から、周期・回文を調べ、suffix arrayとLCPによる標準的な接尾辞索引へ進む。次に有限状態への同値化、pattern automaton、Aho–Corasick、subset construction、Suffix Automatonを続けて学ぶ。その後、runの局所変化と再帰的な圧縮文字列で、明示展開せずに列を扱う。rolling fingerprintはデータ構造章、automaton上の計数はDP章へ接続する。
導入対象の目安: 水色(1200–1599)。prefix・suffix・一致長・有限状態という文字列の共有単位を学ぶ入口。
- Trieで共有接頭辞を索引化する — 水色(1200–1599)
共有prefixを木にし、通過数・辞書順・文字遷移をnode上で管理する。
- 接頭辞との一致長を再利用する — 水色(1200–1599)
既に調べた一致区間を再利用する考え方へ進む入口。
- Z algorithmによるprefix matching — 水色(1200–1599)
Z-boxの不変量と再利用範囲を理解し、prefixとの一致長を線形時間で求める。
概念上の親: 接頭辞との一致長を再利用する
- 文字列周期・primitive word — 青色(1600–1999)
prefix一致・border・primitive rootを結び付け、周期の必要十分条件を扱う。
- 回文半径と左右対称区間を特定する — 青色(1600–1999)
中心の左右対称性と既知区間を再利用し、奇数長・偶数長の回文半径を求める。
- 接尾辞の順序とLCPを索引化する — 青色(1600–1999)
suffix arrayとLCPの意味を理解し、ライブラリで得た索引を部分文字列queryへ使う。
- 禁止・要求patternを有限状態へ圧縮する — 青色(1600–1999)
未来の受理条件が同じprefixをまとめ、有限状態へ変換する入口。
- 有限状態automatonの構成 — 青色(1600–1999)
suffixや進行状況を状態に選び、全ての文字に対する遷移を構成する。
概念上の親: 禁止・要求patternを有限状態へ圧縮する
- Aho–Corasick — 黄色(2000–2399)
Trieのfailure linkで最長suffixを保ち、複数patternの検出情報を伝播する。
概念上の親: 禁止・要求patternを有限状態へ圧縮する
- 非決定性automatonのsubset construction — 黄色(2000–2399)
NFAの可能状態集合を一状態へ写し、受理条件と指数的な状態数を評価する。
概念上の親: 禁止・要求patternを有限状態へ圧縮する
- Suffix Automatonで部分文字列集合を表す — 橙色(2400–2799)
endpos同値類・suffix link・cloneを理解し、全部分文字列を線形状態数で表す。
- run-length状態の動的遷移 — 青色(1600–1999)
runのsplit・mergeと長さを管理し、一操作と全体のrun数の変化を評価する。
- 圧縮・反復・再帰文字列へ問い合わせる — 青色(1600–1999)
再帰blockの長さと位置を追い、展開せずに問い合わせや作用の合成を行う。
第7章 数論
整数条件をgcd・合同・素因数指数・約数格子へ翻訳し、有限状態化と反転の基礎を作る。
- 素因数分解と約数構造緑色(800–1199)
- gcd不変量・差分構造水色(1200–1599)
- gcdと整数解の成立条件水色(1200–1599)
- 法上の演算と積の保守緑色(800–1199)
- 法上の四則演算・高速累乗・逆元緑色(800–1199)
- 可逆な非零剰余と剰余 0 因子を含む法上の動的積水色(1200–1599)
- 一次合同・CRTで解の類を統合する青色(1600–1999)
- 整数境界と同値区間を正確に分ける水色(1200–1599)
- 剰余周期と指数法則を利用する青色(1600–1999)
- 乗法的位数から最小周期を求める青色(1600–1999)
- 巡回群を指数化して数える黄色(2000–2399)
- Baby-Step Giant-Step・可逆作用の反復到達探索黄色(2000–2399)
- 格子点転置によるfloor_sum黄色(2000–2399)
- 連分数・Stern–Brocotで有理近似する橙色(2400–2799)
- Stern–Brocot木の経路と祖先橙色(2400–2799)
- 数値半群のconductor以後を一括到達とみなす橙色(2400–2799)
- 標数pのFrobenius恒等式による反復高速化橙色(2400–2799)
- 拡大有限体の表現と四則演算を構成する橙色(2400–2799)
- Gaussian整数・二平方和赤色(2800以上)
- Min_25・Lucy DP型の総和篩赤色(2800以上)
読書順の考え方・対象色の理由
素因数・gcd・Bézoutから、法上の演算と逆元、CRTへ進む。整数境界の正確な扱いを揃えた後、剰余周期・乗法的位数・巡回群の指数化をつなぎ、BSGSで反復到達時刻を探索する。床和と有理近似ではEuclid互除法による縮小を比較し、Stern–Brocot木の経路へ応用する。発展は数値半群、素体でも使えるFrobenius恒等式、拡大有限体、Gaussian整数、総和篩の順に読む。群の計数には約数反転、総和篩には商一定区間という既習の道具を持ち込む。
導入対象の目安: 緑色(800–1199)。素因数・gcd・剰余を整数条件の表現として使い分ける入口。
- 素因数分解と約数構造 — 緑色(800–1199)
試し割りや篩を使い、素因数の指数と約数に条件を分解する。
- gcd不変量・差分構造 — 水色(1200–1599)
差や周期をgcdにまとめ、共通因子と剰余類が保存する条件を示す。
- gcdと整数解の成立条件 — 水色(1200–1599)
拡張EuclidとBézoutから一次不定方程式の一解と全解を導く。
- 法上の演算と積の保守 — 緑色(800–1199)
法上の四則演算と逆元の存在条件を確認し、積の更新へ進む入口。
- 法上の四則演算・高速累乗・逆元 — 緑色(800–1199)
二分累乗と逆元を実装し、整数の割り算と法上の除算を区別する。
概念上の親: 法上の演算と積の保守
- 可逆な非零剰余と剰余 0 因子を含む法上の動的積 — 水色(1200–1599)
逆元で除ける因子を確認し、0の個数と非零因子の積を分けて更新する。
概念上の親: 法上の演算と積の保守
- 一次合同・CRTで解の類を統合する — 青色(1600–1999)
一次合同の可解条件を確認し、非互いに素な法も含めてCRTで統合する。
- 整数境界と同値区間を正確に分ける — 水色(1200–1599)
床関数や整数根が変わる境界を厳密に求め、同じ値の区間をまとめる。
- 剰余周期と指数法則を利用する — 青色(1600–1999)
Fermat・Euler型の指数簡約で必要な互いに素条件と周期を確認する。
- 乗法的位数から最小周期を求める — 青色(1600–1999)
群の位数と要素の位数を区別し、約数を割り落として最小周期を求める。
- 巡回群を指数化して数える — 黄色(2000–2399)
巡回群を指数へ写し、位数・gcd・約数の分類で重複なく数える。
- Baby-Step Giant-Step・可逆作用の反復到達探索 — 黄色(2000–2399)
可逆性を使って反復回数を二分し、平方根個の状態を照合する。
- 格子点転置によるfloor_sum — 黄色(2000–2399)
床和を格子点数へ写し、傾きと法の交換からEuclid型の再帰を導く。
- 連分数・Stern–Brocotで有理近似する — 橙色(2400–2799)
連分数や隣接分数の行列式を使い、分母制約下で最良の候補を残す。
- Stern–Brocot木の経路と祖先 — 橙色(2400–2799)
mediantの移動をEuclidの商で圧縮し、巨大な経路と祖先集合を扱う。
- 数値半群のconductor以後を一括到達とみなす — 橙色(2400–2799)
非負整数結合が十分先を覆う条件を証明し、有限prefixだけを調べる。
- 標数pのFrobenius恒等式による反復高速化 — 橙色(2400–2799)
標数による二項係数の消滅を演算子へ適用し、反復と圧縮列の増大を評価する。
- 拡大有限体の表現と四則演算を構成する — 橙色(2400–2799)
既約多項式や基底座標から有限体を構成し、四則演算の実装を正当化する。
- Gaussian整数・二平方和 — 赤色(2800以上)
Gaussian整数の素因数分解と共役を使い、二平方和の構成・計数を行う。
- Min_25・Lucy DP型の総和篩 — 赤色(2800以上)
商の異なる値を状態とする篩を構築し、乗法的関数の総和を高速に計算する。
第8章 組合せ・多項式・線形代数
数え上げを全単射・係数列・線形写像へ変換し、高速変換と構造定理へ接続する。
- 組合せ係数と対称性で数える水色(1200–1599)
- 包除・Möbius反転で重複を補正する水色(1200–1599)
- 約数格子のzeta・Möbius反転青色(1600–1999)
- subset zeta・Möbius変換青色(1600–1999)
- 鏡像法・reflection principle青色(1600–1999)
- monoid exponentiation・連結演算doubling水色(1200–1599)
- 半環行列・min-plus/max-min遷移青色(1600–1999)
- 線形方程式・基底・分離可能変換へ変換する青色(1600–1999)
- 線形方程式・rank青色(1600–1999)
- XOR線形基底青色(1600–1999)
- 分離可能線形変換・Walsh–Hadamard変換黄色(2000–2399)
- Prüfer code・次数制約付きlabel木黄色(2000–2399)
- 群作用・軌道数え上げ黄色(2000–2399)
- 削除・縮約recurrence黄色(2000–2399)
- 行列式による数え上げ黄色(2000–2399)
- 半順序・Dilworth・最大反鎖黄色(2000–2399)
- Matroidの独立性・greedy・線形交差黄色(2000–2399)
- matroid greedy黄色(2000–2399)
- 組合せを生成関数へ符号化する黄色(2000–2399)
- label付き連結成分分解・exponential formula黄色(2000–2399)
- NTT・FFTで畳み込みと相互相関を求める黄色(2000–2399)
- factorial convolutionによる多項式Taylor shift橙色(2400–2799)
- FPS基本演算と多項式の多点評価を行う橙色(2400–2799)
- 多項式の多点評価・補間橙色(2400–2799)
- Bostan–Mori・有理生成関数の係数抽出橙色(2400–2799)
- 母関数方程式・高度な係数抽出橙色(2400–2799)
- Relaxed・online convolution橙色(2400–2799)
- subset convolution橙色(2400–2799)
- BEST定理によるEuler circuit数え上げ橙色(2400–2799)
- Robinson–Schensted対応・Young tableau赤色(2800以上)
- FPS合成・power projection赤色(2800以上)
- 線形matroid交差の乱択rank判定赤色(2800以上)
読書順の考え方・対象色の理由
組合せ係数を入口に、包除による重複補正、約数格子・部分集合上のMöbius反転を続け、反射原理は別系統の直接数え上げ典型として学ぶ。反復合成と半環行列、線形方程式・XOR基底・分離可能変換を揃え、Prüfer符号・群作用・削除縮約・行列式・半順序で計数と構造定理を比較する。matroidの独立性と交換公理を中盤で学び、greedyによる最適化へ接続する。その後、母関数の係数解釈から畳み込み・Taylor shift・FPS・多点評価・有理母関数へ進む。発展的な係数抽出、onlineとsubsetの畳み込み、BEST定理、RSK、FPS合成を経て、rankと乱択を要する線形matroid交差を扱う。
導入対象の目安: 水色(1200–1599)。対象を係数・和・積へ翻訳し、数え方と高速な評価を分ける入口。
- 組合せ係数と対称性で数える — 水色(1200–1599)
通常・Gaussian二項係数、Stirling変換、法上の階乗を使い、rank別計数を基底変換する。
- 包除・Möbius反転で重複を補正する — 水色(1200–1599)
条件の共通部分を数え、交互符号が重複を打ち消す理由を説明する。
- 約数格子のzeta・Möbius反転 — 青色(1600–1999)
約数・倍数の累積値とexact値を区別し、反転でgcd別の個数を取り出す。
概念上の親: 包除・Möbius反転で重複を補正する
- subset zeta・Möbius変換 — 青色(1600–1999)
集合の包含方向に一bitずつ和を集め、zeta変換と逆変換を導く。
概念上の親: 包除・Möbius反転で重複を補正する
- 鏡像法・reflection principle — 青色(1600–1999)
最初に境界を破るpathとの全単射を作り、壁付きの計数を差で表す。
- monoid exponentiation・連結演算doubling — 水色(1200–1599)
結合則と単位元を定義し、数値以外の反復合成にも二分累乗を使う。
- 半環行列・min-plus/max-min遷移 — 青色(1600–1999)
行列の和と積を遷移の選択・連結に対応させ、min-plusなどへ一般化する。
- 線形方程式・基底・分離可能変換へ変換する — 青色(1600–1999)
rank・基底・線形写像を制約と変換の共通言語として学ぶ入口。
- 線形方程式・rank — 青色(1600–1999)
体上の消去法を実装し、rankから可解性と自由度を判断する。
概念上の親: 線形方程式・基底・分離可能変換へ変換する
- XOR線形基底 — 青色(1600–1999)
bit列をF₂ベクトルと見なし、pivot消去で独立性・表現可能性を管理し、affine cosetの最小代表を正規化する。
概念上の親: 線形方程式・基底・分離可能変換へ変換する
- 分離可能線形変換・Walsh–Hadamard変換 — 黄色(2000–2399)
各軸の小変換へ分離し、Walsh–Hadamard変換とXOR畳み込みを導く。
概念上の親: 線形方程式・基底・分離可能変換へ変換する
- Prüfer code・次数制約付きlabel木 — 黄色(2000–2399)
label付き木と列の全単射を理解し、次数を出現回数へ写して数える。
- 群作用・軌道数え上げ — 黄色(2000–2399)
群作用と固定点を定義し、Burnside・Pólyaによる対称性込みの計数を行う。
- 削除・縮約recurrence — 黄色(2000–2399)
辺の削除と縮約が対象をどう分割するかを示し、graphの計数再帰を立てる。
- 行列式による数え上げ — 黄色(2000–2399)
行列木定理やLGV補題の対応を理解し、組合せ対象を行列式で数える。
- 半順序・Dilworth・最大反鎖 — 黄色(2000–2399)
半順序のchain・antichainを整理し、matchingやLDSとの対応を使う。
- Matroidの独立性・greedy・線形交差 — 黄色(2000–2399)
独立性と交換公理を使い、貪欲法の成立範囲を整理する入口。
- matroid greedy — 黄色(2000–2399)
独立性oracleと交換公理から、重み順の選択が最適基底を与えることを示す。
概念上の親: Matroidの独立性・greedy・線形交差
- 組合せを生成関数へ符号化する — 黄色(2000–2399)
組合せ構造の和・積を係数列の演算へ写し、求める係数を定める。
- label付き連結成分分解・exponential formula — 黄色(2000–2399)
根を含む成分や成分集合の一意な分解から、指数型母関数やsubset再帰を立てる。
- NTT・FFTで畳み込みと相互相関を求める — 黄色(2000–2399)
係数積和へ還元し、NTT・FFTの法・長さ・次数の条件を理解して利用する。
- factorial convolutionによる多項式Taylor shift — 橙色(2400–2799)
二項展開の階乗因子を整理し、全係数の平行移動を一回の畳み込みへ還元する。
概念上の親: NTT・FFTで畳み込みと相互相関を求める
- FPS基本演算と多項式の多点評価を行う — 橙色(2400–2799)
定数項と打切り次数の条件を押さえ、Newton反復で逆数・log・expを構成する。
- 多項式の多点評価・補間 — 橙色(2400–2799)
一般点の積木・剰余木と等比点のchirp-zを比較し、評価点の構造から変形と計算量を選ぶ。
概念上の親: FPS基本演算と多項式の多点評価を行う
- Bostan–Mori・有理生成関数の係数抽出 — 橙色(2400–2799)
有理母関数の係数を偶奇で分け、指数を半減する変形を繰り返す。
- 母関数方程式・高度な係数抽出 — 橙色(2400–2799)
Lagrange反転・微分による係数比較・Euler積を、式の条件に合わせて選ぶ。
- Relaxed・online convolution — 橙色(2400–2799)
未確定の係数を参照しないblock分割で、オンラインの係数再帰を高速化する。
- subset convolution — 橙色(2400–2799)
集合サイズ別の変換と反転を組み合わせ、互いに素な分割の畳み込みを求める。
- BEST定理によるEuler circuit数え上げ — 橙色(2400–2799)
有向全域木と出辺順列への対応を導き、BEST定理の数え方を適用する。
- Robinson–Schensted対応・Young tableau — 赤色(2800以上)
挿入対応とYoung図形を理解し、LIS・LDS条件をshapeの計数へ移す。
- FPS合成・power projection — 赤色(2800以上)
FPS合成と転置の対応を理解し、block分割や有理関数への還元を扱う。
- 線形matroid交差の乱択rank判定 — 赤色(2800以上)
二つの線形表現から乱択行列を作り、rankと共通独立集合の大きさを対応させる。
概念上の親: Matroidの独立性・greedy・線形交差
第9章 幾何・凸最適化
orientationなどの幾何predicateから凸境界・傾き・dual penaltyへ進み、候補を構造的に削減する。
- 幾何の基本判定と座標変換水色(1200–1599)
- 円環順序・chord交差青色(1600–1999)
- 凸境界・半平面制約を扱う青色(1600–1999)
- 凸包・支持方向・境界候補青色(1600–1999)
- 半平面制約・凸領域の共通部分黄色(2000–2399)
- Convex Hull Trick・直線包絡黄色(2000–2399)
- 凸性・傾き・限界費用・slope trick青色(1600–1999)
- 一次元凸・単峰最適化青色(1600–1999)
- 分離凸・凹の単調限界値選択青色(1600–1999)
- slope trick黄色(2000–2399)
- fractional programming・比率parametric search青色(1600–1999)
- isotonic regression・PAV橙色(2400–2799)
- Lagrangian relaxation・Aliens trick橙色(2400–2799)
- Monge・monotone minima最適化橙色(2400–2799)
- 二変数の凸区分線形整数最適化橙色(2400–2799)
読書順の考え方・対象色の理由
座標・向き・円環順序から凸包と半平面へ進み、幾何的な実行可能領域を表す。直線包絡を幾何と関数の橋渡しとして学ぶ。凸性の節では一次元の最適化から限界値選択・slope trickへ進み、比率目的を単調判定へ変換するfractional programmingを学ぶ。その後、順序制約のPAV、個数制約を罰則へ移すAliens trick、遷移行列のMonge性を扱う。最後に二変数の凸区分線形整数最適化で、連続的な候補と整数格子の近傍保証を組み合わせる。DP・データ構造・数論の道具がどの条件で再利用できるかを確認する。
導入対象の目安: 水色(1200–1599)。座標と向きによる判定から、凸な境界・関数の最適化へ進む入口。
- 幾何の基本判定と座標変換 — 水色(1200–1599)
外積・端点順・座標変換を用い、退化ケースを含む位置関係を判定する。
- 円環順序・chord交差 — 青色(1600–1999)
円環を切って端点順を線形化し、交互配置と包含構造で交差を扱う。
概念上の親: 幾何の基本判定と座標変換
- 凸境界・半平面制約を扱う — 青色(1600–1999)
凸性によって内部の候補を捨て、境界と半平面で領域を表す入口。
- 凸包・支持方向・境界候補 — 青色(1600–1999)
外積で凸包を構築し、支持方向と境界上の極値を扱う。
概念上の親: 凸境界・半平面制約を扱う
- 半平面制約・凸領域の共通部分 — 黄色(2000–2399)
凸多角形を辺ごとの半平面に変換し、平行移動した全領域への包含を最強の制約で判定する。
概念上の親: 凸境界・半平面制約を扱う
- Convex Hull Trick・直線包絡 — 黄色(2000–2399)
DPなどの候補を一次関数へ写し、傾き・交点順やLi Chao Treeで包絡を保つ。
- 凸性・傾き・限界費用・slope trick — 青色(1600–1999)
差分の単調性を入口に、凸関数の選択・合成・制約付き最適化を見渡す。
- 一次元凸・単峰最適化 — 青色(1600–1999)
単峰性や差分の単調性を証明し、三分探索・整数境界で最適点を求める。
概念上の親: 凸性・傾き・限界費用・slope trick
- 分離凸・凹の単調限界値選択 — 青色(1600–1999)
単調な限界費用の列を導き、heapや閾値計数で必要個数を選ぶ。
概念上の親: 凸性・傾き・限界費用・slope trick
- slope trick — 黄色(2000–2399)
区分線形凸関数を折れ点で表し、関数への操作をheapの更新へ写す。
概念上の親: 凸性・傾き・限界費用・slope trick
- fractional programming・比率parametric search — 青色(1600–1999)
分母の正性を確認し、比率を加法的な判定へ変換して二分探索する。
- isotonic regression・PAV — 橙色(2400–2799)
順序制約に違反するblockの併合が正しい理由を示し、PAVで最適化する。
概念上の親: 凸性・傾き・限界費用・slope trick
- Lagrangian relaxation・Aliens trick — 橙色(2400–2799)
罰則係数による個数単調性に加え、双対ギャップなく復元できる条件を証明する。
- Monge・monotone minima最適化 — 橙色(2400–2799)
Monge性から最適位置の単調性を導き、分割統治やSMAWKの条件を確認する。
- 二変数の凸区分線形整数最適化 — 橙色(2400–2799)
折れ目直線の交点から連続最小候補を作り、整数最適点が入る有限近傍を証明する。