分野別目次

初めてなら第1章の最初の単元から。 学びたい分野があれば、その章から読めます。 単元で考え方を学び、問題に取り組み、分からない前提へ戻って読み進めてください。

単元は読書順です。対象色は基本形を学ぶ目安で、問題の難易度や公式の履修基準とは別です。 直接の前提は各単元で確認できます。

第1章 モデル変換とアルゴリズム設計

問題文の操作を再利用可能な対象・不変量へ言い換え、探索・貪欲・分割手法を選ぶ共通の視点を最初に作る。

  1. 候補数を界して全列挙・有限case分解する緑色(800–1199)
  2. backtracking・可逆な探索状態緑色(800–1199)
  3. 同値な状態を正規化する水色(1200–1599)
  4. 疎なkeyの順序を保ってdense indexへ圧縮する緑色(800–1199)
  5. 局所寄与へ分解して集計順を交換する緑色(800–1199)
  6. 探索空間を分けて照合・再帰分割する水色(1200–1599)
  7. 再帰分割・分割統治水色(1200–1599)
  8. meet-in-the-middle・半分全列挙水色(1200–1599)
  9. 単調境界を証明して探索する緑色(800–1199)
  10. 尺取り法・sliding windowで連続区間を走査する緑色(800–1199)
  11. 交換論から選択順を導く水色(1200–1599)
  12. bitwise greedyによるmask最適化水色(1200–1599)
  13. 成立証明から構成解を復元する水色(1200–1599)
  14. 時間を逆向きにして未来依存を消す水色(1200–1599)
  15. event順にactive集合を更新する水色(1200–1599)
  16. 軽重分類と償却解析で総仕事量を抑える水色(1200–1599)
  17. 単調進行による償却解析水色(1200–1599)
  18. small-to-large・DSU on Tree青色(1600–1999)
  19. 平方根・閾値による軽重分類青色(1600–1999)
  20. parallel binary search・多数境界の判定共有青色(1600–1999)
  21. 基準witnessから変更影響を局所化する青色(1600–1999)
  22. 偶奇不変量からゲームの勝敗を決める青色(1600–1999)
  23. 対話protocolを守って情報を取得する緑色(800–1199)
  24. 情報量下界・query符号設計水色(1200–1599)
  25. 乱択の成功条件と誤り確率を設計する青色(1600–1999)
  26. 乱択代数fingerprint黄色(2000–2399)
  27. kinetic sorting・交差event順序更新橙色(2400–2799)
  28. XOR閾値matchingのbit分割再帰赤色(2800以上)
読書順の考え方・対象色の理由

まず全列挙と可逆な探索から正しい基準解を作り、正規化・座標圧縮・寄与分解で扱う対象を減らす。分割統治と半分全列挙で探索空間を分け、単調探索・尺取り・交換論で候補を捨てる理由を学ぶ。構成解の復元に続けて、逆順処理・event走査・償却解析・parallel binary search・変更影響の局所化まで汎用的な設計手法を学ぶ。その後にゲーム固有の偶奇不変量へ進み、対話と情報量、乱択と誤り評価を学んだ後、kineticな順序更新とXOR閾値matchingを複合的な発展として扱う。

導入対象の目安: 緑色(800–1199)。探索や集計を選ぶときに、答えに必要な条件と、計算を減らす根拠を言葉にするための入口です。

  1. 候補数を界して全列挙・有限case分解する — 緑色(800–1199)

    制約から候補数を見積もり、成功までの探索回数を界する考え方を学ぶ。

  2. backtracking・可逆な探索状態 — 緑色(800–1199)

    再帰と訪問済み管理を使い、選択と取り消しが対応する探索を実装する。

  3. 同値な状態を正規化する — 水色(1200–1599)

    対称性で同じ候補をまとめ、代表だけを残してよい理由を示せるようにする。

  4. 疎なkeyの順序を保ってdense indexへ圧縮する — 緑色(800–1199)

    整列と二分探索を使い、大小関係と実際の距離を区別して添字化する。

  5. 局所寄与へ分解して集計順を交換する — 緑色(800–1199)

    要素・組・値・区間のどれを固定すれば一意に数えられるかを見抜き、総和の順を交換する。

  6. 探索空間を分けて照合・再帰分割する — 水色(1200–1599)

    探索空間を独立に分ける場合と、再帰的な小問題へ分ける場合を区別する入口。

  7. 再帰分割・分割統治 — 水色(1200–1599)

    分割・再帰・併合の役割を分け、重複のない合成と計算量を説明する。

    概念上の親: 探索空間を分けて照合・再帰分割する

  8. meet-in-the-middle・半分全列挙 — 水色(1200–1599)

    全列挙と整列・検索を組み合わせ、指数の半減と照合条件を設計する。

    概念上の親: 探索空間を分けて照合・再帰分割する

  9. 単調境界を証明して探索する — 緑色(800–1199)

    二分探索の実装に加え、判定の単調性と境界の意味を説明する。

  10. 尺取り法・sliding windowで連続区間を走査する — 緑色(800–1199)

    窓の条件とpointerが戻らない理由を定め、全体の走査回数を数える。

  11. 交換論から選択順を導く — 水色(1200–1599)

    選択の直感を交換論法や支配関係で裏付け、反例のある貪欲法を見分ける。

  12. bitwise greedyによるmask最適化 — 水色(1200–1599)

    上位bitの優先性と単調な可否判定を組み合わせてmaskを決める。

  13. 成立証明から構成解を復元する — 水色(1200–1599)

    存在判定の証明に操作列や親情報を対応させ、具体的な解へ戻す。

  14. 時間を逆向きにして未来依存を消す — 水色(1200–1599)

    削除を追加に変えるなど、時間を逆に読むことで扱える操作を増やす。

  15. event順にactive集合を更新する — 水色(1200–1599)

    時刻・座標で整列し、同時eventの順序とactive集合の不変量を保つ。

  16. 軽重分類と償却解析で総仕事量を抑える — 水色(1200–1599)

    一操作の最悪時間から離れ、総仕事量と軽重分類で計算量を設計する入口。

  17. 単調進行による償却解析 — 水色(1200–1599)

    一度だけの削除やpotentialの減少に課金し、操作列全体を評価する。

    概念上の親: 軽重分類と償却解析で総仕事量を抑える

  18. small-to-large・DSU on Tree — 青色(1600–1999)

    併合時の倍増と分割時の半減を使い、重複が消える場合も総走査量を証明する。

    概念上の親: 軽重分類と償却解析で総仕事量を抑える

  19. 平方根・閾値による軽重分類 — 青色(1600–1999)

    頻度や次数で場合分けし、二つの計算量の釣合いから閾値を選ぶ。

    概念上の親: 軽重分類と償却解析で総仕事量を抑える

  20. parallel binary search・多数境界の判定共有 — 青色(1600–1999)

    offline処理と二分探索を組み合わせ、複数queryで判定器の走査を共有する。

  21. 基準witnessから変更影響を局所化する — 青色(1600–1999)

    基準解の実行可能性と最適性、または実行列の保存を証明し、答えが変わり得る変更だけを再計算する。

  22. 偶奇不変量からゲームの勝敗を決める — 青色(1600–1999)

    局面ごとの勝敗再帰が不要な条件を見つけ、手数・終端量の偶奇から成立する戦略を証明する。

  23. 対話protocolを守って情報を取得する — 緑色(800–1199)

    入出力手順・flush・問い合わせ上限を守り、単純な識別手順を実装する。

  24. 情報量下界・query符号設計 — 水色(1200–1599)

    応答で区別できる状態数を数え、bit符号化と復号を設計する。

  25. 乱択の成功条件と誤り確率を設計する — 青色(1600–1999)

    一回の成功確率と試行回数を結び付け、乱択が許す誤りを評価する。

  26. 乱択代数fingerprint — 黄色(2000–2399)

    体やXORへの写像を設計し、代数的な衝突確率を全比較回数まで含めて評価する。

    概念上の親: 乱択の成功条件と誤り確率を設計する

  27. kinetic sorting・交差event順序更新 — 橙色(2400–2799)

    連続的な順序変化を隣接交差に限定し、失効eventと総event数を管理する。

  28. XOR閾値matchingのbit分割再帰 — 赤色(2800以上)

    XOR閾値ごとにpair可能数を最大化するbit分割再帰を組み立て、同一部分集合内と二集合間のmatching数を合成する根拠を証明する。

第2章 データ構造と問い合わせ

問い合わせに必要な要約と更新規則を見抜く視点を先に学び、目的に合うデータ構造の選択へつなげる。

  1. 一次元・二次元累積和と差分で区間情報を線形化する茶色(400–799)
  2. 要素索引と連結リストで局所linkを更新する茶色(400–799)
  3. heap・ordered setで全候補の極値を保つ緑色(800–1199)
  4. priority queue・best-first列挙緑色(800–1199)
  5. ordered set・multisetの動的順序管理緑色(800–1199)
  6. 支配関係から不要な候補を単調stack・queueで削る水色(1200–1599)
  7. 大小関係をCartesian treeへ変換する青色(1600–1999)
  8. 反転数・重み付き接頭辞統計をFenwick Treeで保つ水色(1200–1599)
  9. 結合的な区間要約・区間分解・合成水色(1200–1599)
  10. 区間monoid要約水色(1200–1599)
  11. 区間更新を要約へ作用させる青色(1600–1999)
  12. 有限関数・作用の合成水色(1200–1599)
  13. 冪等演算のoverlap range query・Sparse Table水色(1200–1599)
  14. SWAG・two-stack queue aggregation青色(1600–1999)
  15. Segment Treeのcanonical区間分解青色(1600–1999)
  16. 静的sorted range index・Merge Sort Tree青色(1600–1999)
  17. 動的・implicit Segment Tree青色(1600–1999)
  18. 端点更新型のrun分割管理青色(1600–1999)
  19. 値軸のbucket分割と区間集約水色(1200–1599)
  20. Moの順序で区間問い合わせの差分を更新する青色(1600–1999)
  21. bitsetで集合演算をword並列化する水色(1200–1599)
  22. bit列をTrieで索引化する水色(1200–1599)
  23. 上位bitの支配関係によるXOR minimax青色(1600–1999)
  24. Rolling fingerprintで列の同値性を比較する水色(1200–1599)
  25. 列・文字列のrolling fingerprint水色(1200–1599)
  26. 構造を共有して過去の版を保存・復元する青色(1600–1999)
  27. rollback・DFS入退場の状態復元青色(1600–1999)
  28. 永続data structure・structural sharing黄色(2000–2399)
  29. 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)。必要な操作と保持する情報を整理し、基本コンテナから区間構造へ進む入口。

  1. 一次元・二次元累積和と差分で区間情報を線形化する — 茶色(400–799)

    加算と差分で区間を表し、一次元から二次元の包除へ広げる。

  2. 要素索引と連結リストで局所linkを更新する — 茶色(400–799)

    配列や辞書で要素を索引化し、挿入・削除で変わる前後関係だけを更新する。

  3. heap・ordered setで全候補の極値を保つ — 緑色(800–1199)

    極値の取得と近傍の検索を区別し、heapとordered setを使い分ける入口。

  4. priority queue・best-first列挙 — 緑色(800–1199)

    優先度付きキューで、現在選べる候補だけを管理して順に取り出す。

    概念上の親: heap・ordered setで全候補の極値を保つ

  5. ordered set・multisetの動的順序管理 — 緑色(800–1199)

    前後要素・重複を管理し、二集合に分けて境界と集計値を保つ基本操作を学ぶ。

    概念上の親: heap・ordered setで全候補の極値を保つ

  6. 支配関係から不要な候補を単調stack・queueで削る — 水色(1200–1599)

    将来不要な候補を削る支配関係と、一要素一度の償却計算量を説明する。

  7. 大小関係をCartesian treeへ変換する — 青色(1600–1999)

    単調stackから木を構築し、区間極値と再帰分割が同じ構造になることを使う。

  8. 反転数・重み付き接頭辞統計をFenwick Treeで保つ — 水色(1200–1599)

    座標圧縮と動的prefix和を組み合わせ、反転数や重み付き統計を数える。

  9. 結合的な区間要約・区間分解・合成 — 水色(1200–1599)

    結合則・単位元・順序を区間集約の共通言語として使う入口。

  10. 区間monoid要約 — 水色(1200–1599)

    十分な要約と結合演算を定義し、Segment Treeへ正しく載せる。

    概念上の親: 結合的な区間要約・区間分解・合成

  11. 区間更新を要約へ作用させる — 青色(1600–1999)

    要約に対する作用と作用同士の合成を定義し、遅延評価の整合性を説明する。

  12. 有限関数・作用の合成 — 水色(1200–1599)

    小さな遷移表を関数として合成し、適用順の逆転を避ける。

    概念上の親: 結合的な区間要約・区間分解・合成

  13. 冪等演算のoverlap range query・Sparse Table — 水色(1200–1599)

    冪等性が区間の重複を許す理由を理解し、静的queryをSparse Tableで処理する。

    概念上の親: 結合的な区間要約・区間分解・合成

  14. SWAG・two-stack queue aggregation — 青色(1600–1999)

    非可換な結合順を二つのstackで保ち、窓の集約を償却定数時間にする。

    概念上の親: 結合的な区間要約・区間分解・合成

  15. Segment Treeのcanonical区間分解 — 青色(1600–1999)

    区間を少数のnodeへ分解する性質を、値の集約以外の配置にも使う。

    概念上の親: 結合的な区間要約・区間分解・合成

  16. 静的sorted range index・Merge Sort Tree — 青色(1600–1999)

    区間分解・整列列・prefix和を組み合わせ、二つの軸を持つ問い合わせを処理する。

    概念上の親: Segment Treeのcanonical区間分解

  17. 動的・implicit Segment Tree — 青色(1600–1999)

    通常のSegment Treeを疎なnode生成へ拡張し、座標域とnode数を別々に評価する。

    概念上の親: 結合的な区間要約・区間分解・合成

  18. 端点更新型のrun分割管理 — 青色(1600–1999)

    run分割やactive区間の和集合を管理し、endpoint更新・重複被覆・消去回数の償却を説明する。

  19. 値軸のbucket分割と区間集約 — 水色(1200–1599)

    平方根分割で完全blockと端数を分け、更新とqueryの費用を調整する。

  20. Moの順序で区間問い合わせの差分を更新する — 青色(1600–1999)

    追加・削除可能な集計を作り、query順の変更で端点移動量を抑える。

  21. bitsetで集合演算をword並列化する — 水色(1200–1599)

    真偽配列の演算をbit演算へ写し、word幅を含めた計算量を見積もる。

  22. bit列をTrieで索引化する — 水色(1200–1599)

    整数の大小とXORを上位bitからの分岐に写して検索する。

  23. 上位bitの支配関係によるXOR minimax — 青色(1600–1999)

    上位bitが最大値を支配することを使い、二群への再帰とminimaxを導く。

  24. Rolling fingerprintで列の同値性を比較する — 水色(1200–1599)

    列の一致判定を連結可能な要約へ写し、衝突のある比較として扱う入口。

  25. 列・文字列のrolling fingerprint — 水色(1200–1599)

    prefix hashと連結則を実装し、長さ・指数位置・衝突確率を確認する。

    概念上の親: Rolling fingerprintで列の同値性を比較する

  26. 構造を共有して過去の版を保存・復元する — 青色(1600–1999)

    過去へ戻す操作と過去の版を残す操作の違いを理解する入口。

  27. rollback・DFS入退場の状態復元 — 青色(1600–1999)

    変更前の差分を保存し、DFSや時間分割から戻るたびに不変量を復元する。

    概念上の親: 構造を共有して過去の版を保存・復元する

  28. 永続data structure・structural sharing — 黄色(2000–2399)

    更新pathだけの複製と共有部分の不変性を理解し、複数versionを管理する。

    概念上の親: 構造を共有して過去の版を保存・復元する

  29. Segment Tree Beats — 橙色(2400–2799)

    一括更新が失敗する条件を要約に持たせ、再帰下降の回数まで償却解析する。

第3章 動的計画法

状態と遷移の設計を共通言語にし、集合・列・確率・ゲーム・遷移高速化へ進む土台を作る。

  1. 最小十分状態からDPを設計する緑色(800–1199)
  2. グリッド・多次元表の局所DPを設計する緑色(800–1199)
  3. 資源・容量DP緑色(800–1199)
  4. 列・編集距離・区間合成DP緑色(800–1199)
  5. 列・subsequence DP緑色(800–1199)
  6. LIS・末尾の支配関係水色(1200–1599)
  7. 値域集約による部分列DP水色(1200–1599)
  8. prefix分割DP水色(1200–1599)
  9. 区間合成・領域分割DP水色(1200–1599)
  10. 区間拡張DP青色(1600–1999)
  11. 部分集合・bitmask状態DP水色(1200–1599)
  12. 接頭辞から更新する有限状態DP水色(1200–1599)
  13. 上限制約付き桁DP水色(1200–1599)
  14. automaton上のDP・行列遷移青色(1600–1999)
  15. 繰り上がり・借り・混合基数を状態にするDP青色(1600–1999)
  16. 確率過程・期待値DP水色(1200–1599)
  17. ゲーム状態の勝敗とGrundy数水色(1200–1599)
  18. minimax・得点差・局面値を評価するゲームDP水色(1200–1599)
  19. DP遷移を因数分解・集約して加速する青色(1600–1999)
  20. 固定線形遷移を巨大回数進める青色(1600–1999)
  21. 循環局面の後退解析とminimax距離黄色(2000–2399)
  22. frontier/profile DP・境界状態圧縮黄色(2000–2399)
  23. Steiner tree subset DP橙色(2400–2799)
  24. 大容量unbounded knapsackのeventual linearity橙色(2400–2799)
  25. 期待値の頻度圧縮と加法的ポテンシャル橙色(2400–2799)
  26. 独立な数ゲームの和赤色(2800以上)
読書順の考え方・対象色の理由

最小十分状態を定め、グリッド・容量・列・prefix分割・区間・部分集合という基本的な依存構造を比較する。桁上限・automaton・carryによる有限状態化まで一巡した後、確率とゲームで遷移の評価方法を変える。基本的なDP類型を学んでから遷移最適化と固定線形遷移の累乗へ進み、循環局面の後退解析へ広げる。後半は境界圧縮、Steiner木、巨大容量、期待値の状態削減、数ゲームの和を発展として扱う。列DPのLISと値域集約を比較し、automatonは文字列章、Steiner木は最短路の単元を先に参照する。

導入対象の目安: 緑色(800–1199)。状態・基底・遷移・計算順を明示する習慣を身につける入口。

  1. 最小十分状態からDPを設計する — 緑色(800–1199)

    未来の選択に必要な情報だけを残し、履歴を同じ状態へまとめる。

  2. グリッド・多次元表の局所DPを設計する — 緑色(800–1199)

    二次元以上の添字と依存順を定め、隣接状態から表を埋める。

  3. 資源・容量DP — 緑色(800–1199)

    個数・容量を軸とするナップサック型DPを実装し、更新方向を説明する。

  4. 列・編集距離・区間合成DP — 緑色(800–1199)

    prefix・最後の要素・区間という状態の違いを見渡す入口。

  5. 列・subsequence DP — 緑色(800–1199)

    選ぶ・選ばない遷移と最後の要素を状態にし、同じ要素の重複利用を避ける。

    概念上の親: 列・編集距離・区間合成DP

  6. LIS・末尾の支配関係 — 水色(1200–1599)

    末尾の支配関係で状態を圧縮し、二分探索の境界と復元方法を理解する。

    概念上の親: 列・subsequence DP

  7. 値域集約による部分列DP — 水色(1200–1599)

    列DPの遷移を値域の集約へ写し、Segment Treeと更新順を組み合わせる。

    概念上の親: 列・subsequence DP

  8. prefix分割DP — 水色(1200–1599)

    最後の切れ目を固定し、漏れと重複のない分割の漸化式を立てる。

    概念上の親: 列・編集距離・区間合成DP

  9. 区間合成・領域分割DP — 水色(1200–1599)

    小区間の独立性と長さ順の依存を確認し、分割点を遷移にする。

    概念上の親: 列・編集距離・区間合成DP

  10. 区間拡張DP — 青色(1600–1999)

    訪問済み範囲と現在の端で履歴を圧縮し、移動が往復しても非循環なDPを作る。

    概念上の親: 列・編集距離・区間合成DP

  11. 部分集合・bitmask状態DP — 水色(1200–1599)

    使用集合をbitmaskで持ち、集合の増減と遷移順から指数時間DPを設計する。

  12. 接頭辞から更新する有限状態DP — 水色(1200–1599)

    prefixの有限情報だけを持つDPを、桁の上限や文字列の制約へ使う入口。

  13. 上限制約付き桁DP — 水色(1200–1599)

    tight・先頭の0・残す統計を分け、上限以下の整数を重複なく数える。

    概念上の親: 接頭辞から更新する有限状態DP

  14. automaton上のDP・行列遷移 — 青色(1600–1999)

    構成済みautomatonと位置の直積を使い、禁止状態と受理状態を区別して数える。

    概念上の親: 接頭辞から更新する有限状態DP

  15. 繰り上がり・借り・混合基数を状態にするDP — 青色(1600–1999)

    繰り上がりや借りだけを次の桁へ渡し、通常の桁DPと異なる走査方向を設計する。

  16. 確率過程・期待値DP — 水色(1200–1599)

    一段先で条件分けし、確率・期待値の式と自己ループの移項を扱う。

  17. ゲーム状態の勝敗とGrundy数 — 水色(1200–1599)

    DAG上の勝敗再帰からGrundy数へ進み、独立なゲームの和をXORで評価する。

  18. minimax・得点差・局面値を評価するゲームDP — 水色(1200–1599)

    手番と終端利得を明示し、minimaxや得点差の再帰を実装する。

  19. DP遷移を因数分解・集約して加速する — 青色(1600–1999)

    漸化式の共通項・例外・集約範囲を取り出し、状態数と遷移数を別々に減らす。

  20. 固定線形遷移を巨大回数進める — 青色(1600–1999)

    固定線形遷移を行列や漸化式へ写し、巨大回数の反復を二分累乗する。

  21. 循環局面の後退解析とminimax距離 — 黄色(2000–2399)

    循環する局面でOR・ANDの確定条件を分け、引き分けと有限minimax距離を判定する。

  22. frontier/profile DP・境界状態圧縮 — 黄色(2000–2399)

    境界から離れた情報を忘れ、接続関係を正規化した幅指数の状態を設計する。

  23. Steiner tree subset DP — 橙色(2400–2799)

    terminal集合の分割と多始点最短路を交互に使い、部分解の合成を正当化する。

  24. 大容量unbounded knapsackのeventual linearity — 橙色(2400–2799)

    交換論で例外部分を有限に界し、巨大容量を小さなDPと線形部分へ分ける。

  25. 期待値の頻度圧縮と加法的ポテンシャル — 橙色(2400–2799)

    対称性と線形性で期待値を頻度別関数の和に分離し、終端条件まで較正する。

  26. 独立な数ゲームの和 — 赤色(2800以上)

    partisan gameが数になる条件と数の独立和を理解し、Grundy数との違いを扱う。

第4章 グラフアルゴリズム

対象を頂点と辺へ写して到達可能性を扱えるようにし、連結性・最短路・木・フローへ進む土台を作る。

  1. 状態グラフ探索・到達関係緑色(800–1199)
  2. 状態グラフのモデリングと探索緑色(800–1199)
  3. 推移閉包水色(1200–1599)
  4. 方向別grid scanによる長距離効果の前計算水色(1200–1599)
  5. 二部彩色と成分構造を扱う緑色(800–1199)
  6. 連結成分を管理し縮約する緑色(800–1199)
  7. DSUによる連結成分管理・縮約緑色(800–1199)
  8. 静的graph等式制約のpotential伝播水色(1200–1599)
  9. potential・weighted DSU青色(1600–1999)
  10. 重み付き最短路・経路復元・差分制約緑色(800–1199)
  11. 最短路モデル緑色(800–1199)
  12. 最短路を証明する木・経路の復元水色(1200–1599)
  13. difference constraints・不等式系の最短路化青色(1600–1999)
  14. SCCで閉路・DAG順・2-SATを処理する水色(1200–1599)
  15. DAGのtopological processing緑色(800–1199)
  16. 有向cycle検出・sink/source peeling水色(1200–1599)
  17. SCC・縮約DAG・トポロジカル順序水色(1200–1599)
  18. 2-SAT・含意グラフ青色(1600–1999)
  19. 一意な後続・サイクル・ダブリング水色(1200–1599)
  20. 関数グラフのcycle・tree分解水色(1200–1599)
  21. doubling・binary lifting水色(1200–1599)
  22. cut・cycle性質から最適全域木を構成する水色(1200–1599)
  23. Kruskal順の閾値DSU sweep青色(1600–1999)
  24. lowlinkで橋・関節点を特定する青色(1600–1999)
  25. 次数parityからwalkや選択辺集合を判定・構成する水色(1200–1599)
  26. Euler trail・circuit水色(1200–1599)
  27. 指定次数parityの部分グラフ構成青色(1600–1999)
  28. フロー・マッチング・カットへ帰着する青色(1600–1999)
  29. 二部matching・Hall・Kőnig青色(1600–1999)
  30. 最大流・最小カット青色(1600–1999)
  31. 閉路数・次数構造からgraph coreを調べる水色(1200–1599)
  32. 単一サイクル成分とgraph core水色(1200–1599)
  33. cycle space・fundamental cycle basis青色(1600–1999)
  34. 単調path contraction・DSU jump青色(1600–1999)
  35. near-tree graphのkernel化黄色(2000–2399)
  36. 有向walkの周期・cycle差分gcd黄色(2000–2399)
  37. 下限制約付きflowの実現可能性黄色(2000–2399)
  38. 最小費用流・circulation黄色(2000–2399)
  39. 重み付き二部完全matching黄色(2000–2399)
  40. 平面graph双対・cut/path対応黄色(2000–2399)
  41. path matchingのheap縮約greedy橙色(2400–2799)
  42. 一般グラフの最小重み完全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)。状態と遷移を頂点と辺で表し、距離・連結性・向きの違いを整理する入口。

  1. 状態グラフ探索・到達関係 — 緑色(800–1199)

    入力の頂点以外にも状態を作り、探索と到達関係を使う入口。

  2. 状態グラフのモデリングと探索 — 緑色(800–1199)

    位置と補助情報を一つの頂点にし、状態数・辺数を見積もってBFSやDFSを使う。

    概念上の親: 状態グラフ探索・到達関係

  3. 推移閉包 — 水色(1200–1599)

    到達関係の推移性を行列更新やbitsetでまとめて計算する。

    概念上の親: 状態グラフ探索・到達関係

  4. 方向別grid scanによる長距離効果の前計算 — 水色(1200–1599)

    方向ごとの走査で長距離の影響を前計算し、探索中の判定を軽くする。

    概念上の親: 状態グラフ探索・到達関係

  5. 二部彩色と成分構造を扱う — 緑色(800–1199)

    二部性と部の反転対称性を扱い、連結二部グラフの彩色重複も補正する。

  6. 連結成分を管理し縮約する — 緑色(800–1199)

    連結成分を単位に情報を管理し、探索と成分併合を使い分ける入口。

  7. DSUによる連結成分管理・縮約 — 緑色(800–1199)

    代表と成分サイズを管理し、辺追加による連結性をDSUで処理する。

    概念上の親: 連結成分を管理し縮約する

  8. 静的graph等式制約のpotential伝播 — 水色(1200–1599)

    辺の差やXORを伝播し、閉路の整合性と成分ごとの自由度を確認する。

    概念上の親: 連結成分を管理し縮約する

  9. potential・weighted DSU — 青色(1600–1999)

    DSUの親への差を保ち、経路圧縮・併合時の符号と矛盾判定を導く。

    概念上の親: 連結成分を管理し縮約する

  10. 重み付き最短路・経路復元・差分制約 — 緑色(800–1199)

    辺の重みに合う距離計算を選び、最短路の復元へ進む入口。

  11. 最短路モデル — 緑色(800–1199)

    重みと状態の定義を確認し、Dijkstraなどの標準的な最短路算法を使い分ける。

    概念上の親: 重み付き最短路・経路復元・差分制約

  12. 最短路を証明する木・経路の復元 — 水色(1200–1599)

    距離だけでなく到達元を保持し、最短路条件を満たす木や経路を取り出す。

    概念上の親: 重み付き最短路・経路復元・差分制約

  13. difference constraints・不等式系の最短路化 — 青色(1600–1999)

    不等式を辺へ変換し、負閉路と可解性・最適なpotentialの関係を説明する。

    概念上の親: 重み付き最短路・経路復元・差分制約

  14. SCCで閉路・DAG順・2-SATを処理する — 水色(1200–1599)

    有向グラフの循環部分と非循環部分を区別し、縮約して処理する入口。

  15. DAGのtopological processing — 緑色(800–1199)

    入次数による処理順を作り、有向非循環グラフ上の伝播やDPを実装する。

    概念上の親: SCCで閉路・DAG順・2-SATを処理する

  16. 有向cycle検出・sink/source peeling — 水色(1200–1599)

    DFSの訪問状態や次数零の反復削除から、有向cycleと残る領域を判定する。

    概念上の親: SCCで閉路・DAG順・2-SATを処理する

  17. SCC・縮約DAG・トポロジカル順序 — 水色(1200–1599)

    相互到達性で頂点をまとめ、縮約後がDAGになることを使う。

    概念上の親: SCCで閉路・DAG順・2-SATを処理する

  18. 2-SAT・含意グラフ — 青色(1600–1999)

    二値制約を含意へ変換し、literalと否定のSCCから可解性と代入を得る。

    概念上の親: SCCで閉路・DAG順・2-SATを処理する

  19. 一意な後続・サイクル・ダブリング — 水色(1200–1599)

    後続が一意な遷移をcycleと流入木に分け、反復を圧縮する入口。

  20. 関数グラフのcycle・tree分解 — 水色(1200–1599)

    前周期と周期を分離し、cycleへの流入と巨大回数の移動を扱う。

    概念上の親: 一意な後続・サイクル・ダブリング

  21. doubling・binary lifting — 水色(1200–1599)

    二の冪回の遷移を合成し、行き先や累積値を対数回で求める。

    概念上の親: 一意な後続・サイクル・ダブリング

  22. cut・cycle性質から最適全域木を構成する — 水色(1200–1599)

    DSUやheapを用い、cut・cycle性質で全域木の辺選択を正当化する。

  23. Kruskal順の閾値DSU sweep — 青色(1600–1999)

    辺とqueryを同じ重み順に処理し、連結する閾値と同重みの扱いを整理する。

    概念上の親: cut・cycle性質から最適全域木を構成する

  24. lowlinkで橋・関節点を特定する — 青色(1600–1999)

    DFS木と後退辺を区別し、lowlinkの不変量から橋・関節点を判定する。

  25. 次数parityからwalkや選択辺集合を判定・構成する — 水色(1200–1599)

    次数と連結性から全辺を使う歩道や選択辺集合の条件を読む入口。

  26. Euler trail・circuit — 水色(1200–1599)

    次数条件を理解し、辺を一度ずつ使うHierholzer法を実装する。

    概念上の親: 次数parityからwalkや選択辺集合を判定・構成する

  27. 指定次数parityの部分グラフ構成 — 青色(1600–1999)

    木の葉から奇偶条件を確定し、指定した奇数次数集合を実現する。

    概念上の親: 次数parityからwalkや選択辺集合を判定・構成する

  28. フロー・マッチング・カットへ帰着する — 青色(1600–1999)

    割当て・容量・cutの制約を読み、matchingとflowへの還元を選ぶ入口。

  29. 二部matching・Hall・Kőnig — 青色(1600–1999)

    増加路を理解し、Hall条件と最小頂点被覆を割当て問題へ使う。

    概念上の親: フロー・マッチング・カットへ帰着する

  30. 最大流・最小カット — 青色(1600–1999)

    残余グラフとcutの意味を理解し、選択・排反を容量networkへ還元する。

    概念上の親: フロー・マッチング・カットへ帰着する

  31. 閉路数・次数構造からgraph coreを調べる — 水色(1200–1599)

    辺数と頂点数から閉路数を読み、次数条件で残る核を取り出す入口。

  32. 単一サイクル成分とgraph core — 水色(1200–1599)

    成分のE−V+1から閉路数を読み、必要なら葉を剥がして残るcoreを調べる。

    概念上の親: 閉路数・次数構造からgraph coreを調べる

  33. cycle space・fundamental cycle basis — 青色(1600–1999)

    非木辺と基本cycleを対応させ、偶数次数の辺集合をF₂上の基底で表し、辺ラベルによるcycle空間の線形像をXOR spanへ移す。

  34. 単調path contraction・DSU jump — 青色(1600–1999)

    確定した区間を次未処理pointerで飛ばし、削除済み部分を再走査しない。

  35. near-tree graphのkernel化 — 黄色(2000–2399)

    葉と次数2のchainを答えを保って縮約し、余分な辺数で残るサイズを界する。

  36. 有向walkの周期・cycle差分gcd — 黄色(2000–2399)

    SCC内の閉路長を差分のgcdでまとめ、巨大歩数の到達条件を周期へ写す。

  37. 下限制約付きflowの実現可能性 — 黄色(2000–2399)

    下限を需要へ移し、補助source・sinkでcirculationの可解性を判定する。

    概念上の親: フロー・マッチング・カットへ帰着する

  38. 最小費用流・circulation — 黄色(2000–2399)

    残余辺の費用とpotentialを理解し、流量別の最小費用へ還元する。

    概念上の親: フロー・マッチング・カットへ帰着する

  39. 重み付き二部完全matching — 黄色(2000–2399)

    assignmentの双対potentialとtight edgeを理解し、Hungarian法や費用流を選ぶ。

    概念上の親: フロー・マッチング・カットへ帰着する

  40. 平面graph双対・cut/path対応 — 黄色(2000–2399)

    平面埋め込みのfaceを構成し、primalのcutとdualのpath・cycleを対応させる。

  41. path matchingのheap縮約greedy — 橙色(2400–2799)

    選んだ辺の近傍を補正して縮約し、各cardinalityの最適値が得られる理由を示す。

  42. 一般グラフの最小重み完全matching — 赤色(2800以上)

    奇cycleのblossom縮約またはTutte多項式を使う一般matchingの理論を学ぶ。

第5章 木構造

一般グラフから独立させ、根・部分木・一意path・separatorという木固有の不変量を体系的に積み上げる。

  1. 基準点からの木距離・剰余類・直径・中心水色(1200–1599)
  2. 木DP・集約・rerooting水色(1200–1599)
  3. 根付き木DP・部分木集約水色(1200–1599)
  4. rerooting・全方位木DP青色(1600–1999)
  5. 木のancestor・部分木・pathを索引化する水色(1200–1599)
  6. Euler順による部分木区間化水色(1200–1599)
  7. ancestor query・LCA水色(1200–1599)
  8. Heavy-Light Decomposition青色(1600–1999)
  9. virtual tree・auxiliary tree黄色(2000–2399)
  10. 対称性・深さ・label区間で巨大な完全二分木を数える水色(1200–1599)
  11. laminar区間族の包含木構築青色(1600–1999)
  12. DSU merge tree・Kruskal reconstruction tree青色(1600–1999)
  13. 木の均衡分離点から重心分解へ進む黄色(2000–2399)
  14. 加法的tree metric復元橙色(2400–2799)
  15. 01 on Tree・親先行順序のcluster縮約橙色(2400–2799)
  16. heavy path上の多項式木DP橙色(2400–2799)
  17. rake・compressで動的木DPを保つ橙色(2400–2799)
  18. 資源DPを引数で渡すHLRecDP赤色(2800以上)
読書順の考え方・対象色の理由

一意な経路と距離・直径を確認し、根付き木DP・rerootingで部分木と全方位集約を学ぶ。Euler順・LCA・HLD・virtual treeで部分木・祖先・pathを扱う一般的なtoolkitを揃えた後、暗黙の完全二分木を展開せずに数える。続いて包含関係や併合履歴を木にする方法、重心分解、距離からの木の復元、親先行順序の縮約へ進む。後半は多項式木DP、rake・compressによる動的木DP、資源DPを渡すHLRecDPを扱う。多項式木DPでは代数章の畳み込みを先に学ぶ。

導入対象の目安: 水色(1200–1599)。探索で得る木の距離・祖先・部分木を、集約と分解の共通の土台にする入口。

  1. 基準点からの木距離・剰余類・直径・中心 — 水色(1200–1599)

    一意経路と直径端点の性質を理解し、少数の距離計算で全頂点を評価する。

  2. 木DP・集約・rerooting — 水色(1200–1599)

    部分木から親へ渡す要約を定め、根の移動やpath上の合成へ進む入口。

  3. 根付き木DP・部分木集約 — 水色(1200–1599)

    子部分木の独立性と親へ渡す状態を定め、bottom-upに合成する。

    概念上の親: 木DP・集約・rerooting

  4. rerooting・全方位木DP — 青色(1600–1999)

    各辺の両側の情報を設計し、prefix・suffix合成で全根の答えを求める。

    概念上の親: 木DP・集約・rerooting

  5. 木のancestor・部分木・pathを索引化する — 水色(1200–1599)

    木を区間や祖先関係へ写し、配列上の算法へ接続する入口。

  6. Euler順による部分木区間化 — 水色(1200–1599)

    DFS時刻で部分木が連続区間になることを使い、区間queryへ写す。

    概念上の親: 木のancestor・部分木・pathを索引化する

  7. ancestor query・LCA — 水色(1200–1599)

    深さ調整とbinary liftingを用い、LCA・祖先・距離のqueryを処理する。

    概念上の親: 木のancestor・部分木・pathを索引化する

  8. Heavy-Light Decomposition — 青色(1600–1999)

    軽い辺の回数を界し、pathを少数の区間に分解して順序付きqueryを処理する。

    概念上の親: 木のancestor・部分木・pathを索引化する

  9. virtual tree・auxiliary tree — 黄色(2000–2399)

    Euler順と隣接LCAで必要な分岐点だけを残し、小さな木上で計算する。

    概念上の親: 木のancestor・部分木・pathを索引化する

  10. 対称性・深さ・label区間で巨大な完全二分木を数える — 水色(1200–1599)

    二冪・深さ・heap番号の区間を使い、巨大な完全二分木を展開せず数える。

  11. laminar区間族の包含木構築 — 青色(1600–1999)

    包含条件を確認し、端点の整列とstackで直接の親を構築する。

  12. DSU merge tree・Kruskal reconstruction tree — 青色(1600–1999)

    DSUの併合履歴を木に保存し、時刻や閾値のqueryを祖先関係へ写す。

  13. 木の均衡分離点から重心分解へ進む — 黄色(2000–2399)

    重み付きの一点分離と、頂点数を半減させる再帰分解を区別し、分離点を通る寄与を集計する。

  14. 加法的tree metric復元 — 橙色(2400–2799)

    距離行列から接続先と辺長を復元し、加法性と全距離の整合を検証する。

  15. 01 on Tree・親先行順序のcluster縮約 — 橙色(2400–2799)

    親先行制約の交換比較量を導き、clusterをheapとDSUで縮約する。

  16. heavy path上の多項式木DP — 橙色(2400–2799)

    多項式の木DPをheavy path上の合成にまとめ、軽い部分木の総費用を評価する。

  17. rake・compressで動的木DPを保つ — 橙色(2400–2799)

    境界付きclusterのrake・compressを設計し、更新の影響を木DPの合成で伝播する。

  18. 資源DPを引数で渡すHLRecDP — 赤色(2800以上)

    資源DPを再帰の引数にし、軽い子への重複呼出しまで含めて計算量を証明する。

第6章 文字列アルゴリズム

接頭辞・接尾辞・一致長などの文字列状態を共通言語にし、各種の照合・索引法へ進む土台を作る。

  1. Trieで共有接頭辞を索引化する水色(1200–1599)
  2. 接頭辞との一致長を再利用する水色(1200–1599)
  3. Z algorithmによるprefix matching水色(1200–1599)
  4. 文字列周期・primitive word青色(1600–1999)
  5. 回文半径と左右対称区間を特定する青色(1600–1999)
  6. 接尾辞の順序とLCPを索引化する青色(1600–1999)
  7. 禁止・要求patternを有限状態へ圧縮する青色(1600–1999)
  8. 有限状態automatonの構成青色(1600–1999)
  9. Aho–Corasick黄色(2000–2399)
  10. 非決定性automatonのsubset construction黄色(2000–2399)
  11. Suffix Automatonで部分文字列集合を表す橙色(2400–2799)
  12. run-length状態の動的遷移青色(1600–1999)
  13. 圧縮・反復・再帰文字列へ問い合わせる青色(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・一致長・有限状態という文字列の共有単位を学ぶ入口。

  1. Trieで共有接頭辞を索引化する — 水色(1200–1599)

    共有prefixを木にし、通過数・辞書順・文字遷移をnode上で管理する。

  2. 接頭辞との一致長を再利用する — 水色(1200–1599)

    既に調べた一致区間を再利用する考え方へ進む入口。

  3. Z algorithmによるprefix matching — 水色(1200–1599)

    Z-boxの不変量と再利用範囲を理解し、prefixとの一致長を線形時間で求める。

    概念上の親: 接頭辞との一致長を再利用する

  4. 文字列周期・primitive word — 青色(1600–1999)

    prefix一致・border・primitive rootを結び付け、周期の必要十分条件を扱う。

  5. 回文半径と左右対称区間を特定する — 青色(1600–1999)

    中心の左右対称性と既知区間を再利用し、奇数長・偶数長の回文半径を求める。

  6. 接尾辞の順序とLCPを索引化する — 青色(1600–1999)

    suffix arrayとLCPの意味を理解し、ライブラリで得た索引を部分文字列queryへ使う。

  7. 禁止・要求patternを有限状態へ圧縮する — 青色(1600–1999)

    未来の受理条件が同じprefixをまとめ、有限状態へ変換する入口。

  8. 有限状態automatonの構成 — 青色(1600–1999)

    suffixや進行状況を状態に選び、全ての文字に対する遷移を構成する。

    概念上の親: 禁止・要求patternを有限状態へ圧縮する

  9. Aho–Corasick — 黄色(2000–2399)

    Trieのfailure linkで最長suffixを保ち、複数patternの検出情報を伝播する。

    概念上の親: 禁止・要求patternを有限状態へ圧縮する

  10. 非決定性automatonのsubset construction — 黄色(2000–2399)

    NFAの可能状態集合を一状態へ写し、受理条件と指数的な状態数を評価する。

    概念上の親: 禁止・要求patternを有限状態へ圧縮する

  11. Suffix Automatonで部分文字列集合を表す — 橙色(2400–2799)

    endpos同値類・suffix link・cloneを理解し、全部分文字列を線形状態数で表す。

  12. run-length状態の動的遷移 — 青色(1600–1999)

    runのsplit・mergeと長さを管理し、一操作と全体のrun数の変化を評価する。

  13. 圧縮・反復・再帰文字列へ問い合わせる — 青色(1600–1999)

    再帰blockの長さと位置を追い、展開せずに問い合わせや作用の合成を行う。

第7章 数論

整数条件をgcd・合同・素因数指数・約数格子へ翻訳し、有限状態化と反転の基礎を作る。

  1. 素因数分解と約数構造緑色(800–1199)
  2. gcd不変量・差分構造水色(1200–1599)
  3. gcdと整数解の成立条件水色(1200–1599)
  4. 法上の演算と積の保守緑色(800–1199)
  5. 法上の四則演算・高速累乗・逆元緑色(800–1199)
  6. 可逆な非零剰余と剰余 0 因子を含む法上の動的積水色(1200–1599)
  7. 一次合同・CRTで解の類を統合する青色(1600–1999)
  8. 整数境界と同値区間を正確に分ける水色(1200–1599)
  9. 剰余周期と指数法則を利用する青色(1600–1999)
  10. 乗法的位数から最小周期を求める青色(1600–1999)
  11. 巡回群を指数化して数える黄色(2000–2399)
  12. Baby-Step Giant-Step・可逆作用の反復到達探索黄色(2000–2399)
  13. 格子点転置によるfloor_sum黄色(2000–2399)
  14. 連分数・Stern–Brocotで有理近似する橙色(2400–2799)
  15. Stern–Brocot木の経路と祖先橙色(2400–2799)
  16. 数値半群のconductor以後を一括到達とみなす橙色(2400–2799)
  17. 標数pのFrobenius恒等式による反復高速化橙色(2400–2799)
  18. 拡大有限体の表現と四則演算を構成する橙色(2400–2799)
  19. Gaussian整数・二平方和赤色(2800以上)
  20. Min_25・Lucy DP型の総和篩赤色(2800以上)
読書順の考え方・対象色の理由

素因数・gcd・Bézoutから、法上の演算と逆元、CRTへ進む。整数境界の正確な扱いを揃えた後、剰余周期・乗法的位数・巡回群の指数化をつなぎ、BSGSで反復到達時刻を探索する。床和と有理近似ではEuclid互除法による縮小を比較し、Stern–Brocot木の経路へ応用する。発展は数値半群、素体でも使えるFrobenius恒等式、拡大有限体、Gaussian整数、総和篩の順に読む。群の計数には約数反転、総和篩には商一定区間という既習の道具を持ち込む。

導入対象の目安: 緑色(800–1199)。素因数・gcd・剰余を整数条件の表現として使い分ける入口。

  1. 素因数分解と約数構造 — 緑色(800–1199)

    試し割りや篩を使い、素因数の指数と約数に条件を分解する。

  2. gcd不変量・差分構造 — 水色(1200–1599)

    差や周期をgcdにまとめ、共通因子と剰余類が保存する条件を示す。

  3. gcdと整数解の成立条件 — 水色(1200–1599)

    拡張EuclidとBézoutから一次不定方程式の一解と全解を導く。

  4. 法上の演算と積の保守 — 緑色(800–1199)

    法上の四則演算と逆元の存在条件を確認し、積の更新へ進む入口。

  5. 法上の四則演算・高速累乗・逆元 — 緑色(800–1199)

    二分累乗と逆元を実装し、整数の割り算と法上の除算を区別する。

    概念上の親: 法上の演算と積の保守

  6. 可逆な非零剰余と剰余 0 因子を含む法上の動的積 — 水色(1200–1599)

    逆元で除ける因子を確認し、0の個数と非零因子の積を分けて更新する。

    概念上の親: 法上の演算と積の保守

  7. 一次合同・CRTで解の類を統合する — 青色(1600–1999)

    一次合同の可解条件を確認し、非互いに素な法も含めてCRTで統合する。

  8. 整数境界と同値区間を正確に分ける — 水色(1200–1599)

    床関数や整数根が変わる境界を厳密に求め、同じ値の区間をまとめる。

  9. 剰余周期と指数法則を利用する — 青色(1600–1999)

    Fermat・Euler型の指数簡約で必要な互いに素条件と周期を確認する。

  10. 乗法的位数から最小周期を求める — 青色(1600–1999)

    群の位数と要素の位数を区別し、約数を割り落として最小周期を求める。

  11. 巡回群を指数化して数える — 黄色(2000–2399)

    巡回群を指数へ写し、位数・gcd・約数の分類で重複なく数える。

  12. Baby-Step Giant-Step・可逆作用の反復到達探索 — 黄色(2000–2399)

    可逆性を使って反復回数を二分し、平方根個の状態を照合する。

  13. 格子点転置によるfloor_sum — 黄色(2000–2399)

    床和を格子点数へ写し、傾きと法の交換からEuclid型の再帰を導く。

  14. 連分数・Stern–Brocotで有理近似する — 橙色(2400–2799)

    連分数や隣接分数の行列式を使い、分母制約下で最良の候補を残す。

  15. Stern–Brocot木の経路と祖先 — 橙色(2400–2799)

    mediantの移動をEuclidの商で圧縮し、巨大な経路と祖先集合を扱う。

  16. 数値半群のconductor以後を一括到達とみなす — 橙色(2400–2799)

    非負整数結合が十分先を覆う条件を証明し、有限prefixだけを調べる。

  17. 標数pのFrobenius恒等式による反復高速化 — 橙色(2400–2799)

    標数による二項係数の消滅を演算子へ適用し、反復と圧縮列の増大を評価する。

  18. 拡大有限体の表現と四則演算を構成する — 橙色(2400–2799)

    既約多項式や基底座標から有限体を構成し、四則演算の実装を正当化する。

  19. Gaussian整数・二平方和 — 赤色(2800以上)

    Gaussian整数の素因数分解と共役を使い、二平方和の構成・計数を行う。

  20. Min_25・Lucy DP型の総和篩 — 赤色(2800以上)

    商の異なる値を状態とする篩を構築し、乗法的関数の総和を高速に計算する。

第8章 組合せ・多項式・線形代数

数え上げを全単射・係数列・線形写像へ変換し、高速変換と構造定理へ接続する。

  1. 組合せ係数と対称性で数える水色(1200–1599)
  2. 包除・Möbius反転で重複を補正する水色(1200–1599)
  3. 約数格子のzeta・Möbius反転青色(1600–1999)
  4. subset zeta・Möbius変換青色(1600–1999)
  5. 鏡像法・reflection principle青色(1600–1999)
  6. monoid exponentiation・連結演算doubling水色(1200–1599)
  7. 半環行列・min-plus/max-min遷移青色(1600–1999)
  8. 線形方程式・基底・分離可能変換へ変換する青色(1600–1999)
  9. 線形方程式・rank青色(1600–1999)
  10. XOR線形基底青色(1600–1999)
  11. 分離可能線形変換・Walsh–Hadamard変換黄色(2000–2399)
  12. Prüfer code・次数制約付きlabel木黄色(2000–2399)
  13. 群作用・軌道数え上げ黄色(2000–2399)
  14. 削除・縮約recurrence黄色(2000–2399)
  15. 行列式による数え上げ黄色(2000–2399)
  16. 半順序・Dilworth・最大反鎖黄色(2000–2399)
  17. Matroidの独立性・greedy・線形交差黄色(2000–2399)
  18. matroid greedy黄色(2000–2399)
  19. 組合せを生成関数へ符号化する黄色(2000–2399)
  20. label付き連結成分分解・exponential formula黄色(2000–2399)
  21. NTT・FFTで畳み込みと相互相関を求める黄色(2000–2399)
  22. factorial convolutionによる多項式Taylor shift橙色(2400–2799)
  23. FPS基本演算と多項式の多点評価を行う橙色(2400–2799)
  24. 多項式の多点評価・補間橙色(2400–2799)
  25. Bostan–Mori・有理生成関数の係数抽出橙色(2400–2799)
  26. 母関数方程式・高度な係数抽出橙色(2400–2799)
  27. Relaxed・online convolution橙色(2400–2799)
  28. subset convolution橙色(2400–2799)
  29. BEST定理によるEuler circuit数え上げ橙色(2400–2799)
  30. Robinson–Schensted対応・Young tableau赤色(2800以上)
  31. FPS合成・power projection赤色(2800以上)
  32. 線形matroid交差の乱択rank判定赤色(2800以上)
読書順の考え方・対象色の理由

組合せ係数を入口に、包除による重複補正、約数格子・部分集合上のMöbius反転を続け、反射原理は別系統の直接数え上げ典型として学ぶ。反復合成と半環行列、線形方程式・XOR基底・分離可能変換を揃え、Prüfer符号・群作用・削除縮約・行列式・半順序で計数と構造定理を比較する。matroidの独立性と交換公理を中盤で学び、greedyによる最適化へ接続する。その後、母関数の係数解釈から畳み込み・Taylor shift・FPS・多点評価・有理母関数へ進む。発展的な係数抽出、onlineとsubsetの畳み込み、BEST定理、RSK、FPS合成を経て、rankと乱択を要する線形matroid交差を扱う。

導入対象の目安: 水色(1200–1599)。対象を係数・和・積へ翻訳し、数え方と高速な評価を分ける入口。

  1. 組合せ係数と対称性で数える — 水色(1200–1599)

    通常・Gaussian二項係数、Stirling変換、法上の階乗を使い、rank別計数を基底変換する。

  2. 包除・Möbius反転で重複を補正する — 水色(1200–1599)

    条件の共通部分を数え、交互符号が重複を打ち消す理由を説明する。

  3. 約数格子のzeta・Möbius反転 — 青色(1600–1999)

    約数・倍数の累積値とexact値を区別し、反転でgcd別の個数を取り出す。

    概念上の親: 包除・Möbius反転で重複を補正する

  4. subset zeta・Möbius変換 — 青色(1600–1999)

    集合の包含方向に一bitずつ和を集め、zeta変換と逆変換を導く。

    概念上の親: 包除・Möbius反転で重複を補正する

  5. 鏡像法・reflection principle — 青色(1600–1999)

    最初に境界を破るpathとの全単射を作り、壁付きの計数を差で表す。

  6. monoid exponentiation・連結演算doubling — 水色(1200–1599)

    結合則と単位元を定義し、数値以外の反復合成にも二分累乗を使う。

  7. 半環行列・min-plus/max-min遷移 — 青色(1600–1999)

    行列の和と積を遷移の選択・連結に対応させ、min-plusなどへ一般化する。

  8. 線形方程式・基底・分離可能変換へ変換する — 青色(1600–1999)

    rank・基底・線形写像を制約と変換の共通言語として学ぶ入口。

  9. 線形方程式・rank — 青色(1600–1999)

    体上の消去法を実装し、rankから可解性と自由度を判断する。

    概念上の親: 線形方程式・基底・分離可能変換へ変換する

  10. XOR線形基底 — 青色(1600–1999)

    bit列をF₂ベクトルと見なし、pivot消去で独立性・表現可能性を管理し、affine cosetの最小代表を正規化する。

    概念上の親: 線形方程式・基底・分離可能変換へ変換する

  11. 分離可能線形変換・Walsh–Hadamard変換 — 黄色(2000–2399)

    各軸の小変換へ分離し、Walsh–Hadamard変換とXOR畳み込みを導く。

    概念上の親: 線形方程式・基底・分離可能変換へ変換する

  12. Prüfer code・次数制約付きlabel木 — 黄色(2000–2399)

    label付き木と列の全単射を理解し、次数を出現回数へ写して数える。

  13. 群作用・軌道数え上げ — 黄色(2000–2399)

    群作用と固定点を定義し、Burnside・Pólyaによる対称性込みの計数を行う。

  14. 削除・縮約recurrence — 黄色(2000–2399)

    辺の削除と縮約が対象をどう分割するかを示し、graphの計数再帰を立てる。

  15. 行列式による数え上げ — 黄色(2000–2399)

    行列木定理やLGV補題の対応を理解し、組合せ対象を行列式で数える。

  16. 半順序・Dilworth・最大反鎖 — 黄色(2000–2399)

    半順序のchain・antichainを整理し、matchingやLDSとの対応を使う。

  17. Matroidの独立性・greedy・線形交差 — 黄色(2000–2399)

    独立性と交換公理を使い、貪欲法の成立範囲を整理する入口。

  18. matroid greedy — 黄色(2000–2399)

    独立性oracleと交換公理から、重み順の選択が最適基底を与えることを示す。

    概念上の親: Matroidの独立性・greedy・線形交差

  19. 組合せを生成関数へ符号化する — 黄色(2000–2399)

    組合せ構造の和・積を係数列の演算へ写し、求める係数を定める。

  20. label付き連結成分分解・exponential formula — 黄色(2000–2399)

    根を含む成分や成分集合の一意な分解から、指数型母関数やsubset再帰を立てる。

  21. NTT・FFTで畳み込みと相互相関を求める — 黄色(2000–2399)

    係数積和へ還元し、NTT・FFTの法・長さ・次数の条件を理解して利用する。

  22. factorial convolutionによる多項式Taylor shift — 橙色(2400–2799)

    二項展開の階乗因子を整理し、全係数の平行移動を一回の畳み込みへ還元する。

    概念上の親: NTT・FFTで畳み込みと相互相関を求める

  23. FPS基本演算と多項式の多点評価を行う — 橙色(2400–2799)

    定数項と打切り次数の条件を押さえ、Newton反復で逆数・log・expを構成する。

  24. 多項式の多点評価・補間 — 橙色(2400–2799)

    一般点の積木・剰余木と等比点のchirp-zを比較し、評価点の構造から変形と計算量を選ぶ。

    概念上の親: FPS基本演算と多項式の多点評価を行う

  25. Bostan–Mori・有理生成関数の係数抽出 — 橙色(2400–2799)

    有理母関数の係数を偶奇で分け、指数を半減する変形を繰り返す。

  26. 母関数方程式・高度な係数抽出 — 橙色(2400–2799)

    Lagrange反転・微分による係数比較・Euler積を、式の条件に合わせて選ぶ。

  27. Relaxed・online convolution — 橙色(2400–2799)

    未確定の係数を参照しないblock分割で、オンラインの係数再帰を高速化する。

  28. subset convolution — 橙色(2400–2799)

    集合サイズ別の変換と反転を組み合わせ、互いに素な分割の畳み込みを求める。

  29. BEST定理によるEuler circuit数え上げ — 橙色(2400–2799)

    有向全域木と出辺順列への対応を導き、BEST定理の数え方を適用する。

  30. Robinson–Schensted対応・Young tableau — 赤色(2800以上)

    挿入対応とYoung図形を理解し、LIS・LDS条件をshapeの計数へ移す。

  31. FPS合成・power projection — 赤色(2800以上)

    FPS合成と転置の対応を理解し、block分割や有理関数への還元を扱う。

  32. 線形matroid交差の乱択rank判定 — 赤色(2800以上)

    二つの線形表現から乱択行列を作り、rankと共通独立集合の大きさを対応させる。

    概念上の親: Matroidの独立性・greedy・線形交差

第9章 幾何・凸最適化

orientationなどの幾何predicateから凸境界・傾き・dual penaltyへ進み、候補を構造的に削減する。

  1. 幾何の基本判定と座標変換水色(1200–1599)
  2. 円環順序・chord交差青色(1600–1999)
  3. 凸境界・半平面制約を扱う青色(1600–1999)
  4. 凸包・支持方向・境界候補青色(1600–1999)
  5. 半平面制約・凸領域の共通部分黄色(2000–2399)
  6. Convex Hull Trick・直線包絡黄色(2000–2399)
  7. 凸性・傾き・限界費用・slope trick青色(1600–1999)
  8. 一次元凸・単峰最適化青色(1600–1999)
  9. 分離凸・凹の単調限界値選択青色(1600–1999)
  10. slope trick黄色(2000–2399)
  11. fractional programming・比率parametric search青色(1600–1999)
  12. isotonic regression・PAV橙色(2400–2799)
  13. Lagrangian relaxation・Aliens trick橙色(2400–2799)
  14. Monge・monotone minima最適化橙色(2400–2799)
  15. 二変数の凸区分線形整数最適化橙色(2400–2799)
読書順の考え方・対象色の理由

座標・向き・円環順序から凸包と半平面へ進み、幾何的な実行可能領域を表す。直線包絡を幾何と関数の橋渡しとして学ぶ。凸性の節では一次元の最適化から限界値選択・slope trickへ進み、比率目的を単調判定へ変換するfractional programmingを学ぶ。その後、順序制約のPAV、個数制約を罰則へ移すAliens trick、遷移行列のMonge性を扱う。最後に二変数の凸区分線形整数最適化で、連続的な候補と整数格子の近傍保証を組み合わせる。DP・データ構造・数論の道具がどの条件で再利用できるかを確認する。

導入対象の目安: 水色(1200–1599)。座標と向きによる判定から、凸な境界・関数の最適化へ進む入口。

  1. 幾何の基本判定と座標変換 — 水色(1200–1599)

    外積・端点順・座標変換を用い、退化ケースを含む位置関係を判定する。

  2. 円環順序・chord交差 — 青色(1600–1999)

    円環を切って端点順を線形化し、交互配置と包含構造で交差を扱う。

    概念上の親: 幾何の基本判定と座標変換

  3. 凸境界・半平面制約を扱う — 青色(1600–1999)

    凸性によって内部の候補を捨て、境界と半平面で領域を表す入口。

  4. 凸包・支持方向・境界候補 — 青色(1600–1999)

    外積で凸包を構築し、支持方向と境界上の極値を扱う。

    概念上の親: 凸境界・半平面制約を扱う

  5. 半平面制約・凸領域の共通部分 — 黄色(2000–2399)

    凸多角形を辺ごとの半平面に変換し、平行移動した全領域への包含を最強の制約で判定する。

    概念上の親: 凸境界・半平面制約を扱う

  6. Convex Hull Trick・直線包絡 — 黄色(2000–2399)

    DPなどの候補を一次関数へ写し、傾き・交点順やLi Chao Treeで包絡を保つ。

  7. 凸性・傾き・限界費用・slope trick — 青色(1600–1999)

    差分の単調性を入口に、凸関数の選択・合成・制約付き最適化を見渡す。

  8. 一次元凸・単峰最適化 — 青色(1600–1999)

    単峰性や差分の単調性を証明し、三分探索・整数境界で最適点を求める。

    概念上の親: 凸性・傾き・限界費用・slope trick

  9. 分離凸・凹の単調限界値選択 — 青色(1600–1999)

    単調な限界費用の列を導き、heapや閾値計数で必要個数を選ぶ。

    概念上の親: 凸性・傾き・限界費用・slope trick

  10. slope trick — 黄色(2000–2399)

    区分線形凸関数を折れ点で表し、関数への操作をheapの更新へ写す。

    概念上の親: 凸性・傾き・限界費用・slope trick

  11. fractional programming・比率parametric search — 青色(1600–1999)

    分母の正性を確認し、比率を加法的な判定へ変換して二分探索する。

  12. isotonic regression・PAV — 橙色(2400–2799)

    順序制約に違反するblockの併合が正しい理由を示し、PAVで最適化する。

    概念上の親: 凸性・傾き・限界費用・slope trick

  13. Lagrangian relaxation・Aliens trick — 橙色(2400–2799)

    罰則係数による個数単調性に加え、双対ギャップなく復元できる条件を証明する。

  14. Monge・monotone minima最適化 — 橙色(2400–2799)

    Monge性から最適位置の単調性を導き、分割統治やSMAWKの条件を確認する。

  15. 二変数の凸区分線形整数最適化 — 橙色(2400–2799)

    折れ目直線の交点から連続最小候補を作り、整数最適点が入る有限近傍を証明する。