グラフアルゴリズム
概要
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で締めくくる。
グラフモデルと構造
対象を頂点・辺・木・有向遷移として構造化する。
考え方
関係を頂点と辺へ写したら、向き、重み、状態に必要な情報を確認する。探索・連結性・最短路・有向構造の基本を揃え、経路の存在から流量・matching・閉路の線形構造へ広げる。
成立条件と計算量
V頂点E辺の明示的な構築だけでもO(V+E)が必要。暗黙の状態グラフでは元入力より状態数が大きくなるため、遷移生成の総数を見積もる。各節で必要な構造を確認し、graphという形式だけから算法を決めない。
章の構成
項目は各章の読書順に並べています。親子関係は順序と独立しているため、階層を字下げで表さず、子Unitには「概念上の親」を示します。導入項目は関連手法の見取り図で、発展的なUnitは対象色を目安に後から戻って学べます。
- 状態グラフ探索・到達関係 — 緑色(導入)
- 状態グラフのモデリングと探索 — 緑色。概念上の親: 状態グラフ探索・到達関係
- 推移閉包 — 水色。概念上の親: 状態グラフ探索・到達関係
- 方向別grid scanによる長距離効果の前計算 — 水色。概念上の親: 状態グラフ探索・到達関係
- 二部彩色と成分構造を扱う — 緑色
- 連結成分を管理し縮約する — 緑色(導入)
- DSUによる連結成分管理・縮約 — 緑色。概念上の親: 連結成分を管理し縮約する
- 静的graph等式制約のpotential伝播 — 水色。概念上の親: 連結成分を管理し縮約する
- potential・weighted DSU — 青色。概念上の親: 連結成分を管理し縮約する
- 重み付き最短路・経路復元・差分制約 — 緑色(導入)
- 最短路モデル — 緑色。概念上の親: 重み付き最短路・経路復元・差分制約
- 最短路を証明する木・経路の復元 — 水色。概念上の親: 重み付き最短路・経路復元・差分制約
- difference constraints・不等式系の最短路化 — 青色。概念上の親: 重み付き最短路・経路復元・差分制約
- SCCで閉路・DAG順・2-SATを処理する — 水色(導入)
- DAGのtopological processing — 緑色。概念上の親: SCCで閉路・DAG順・2-SATを処理する
- 有向cycle検出・sink/source peeling — 水色。概念上の親: SCCで閉路・DAG順・2-SATを処理する
- SCC・縮約DAG・トポロジカル順序 — 水色。概念上の親: SCCで閉路・DAG順・2-SATを処理する
- 2-SAT・含意グラフ — 青色。概念上の親: SCCで閉路・DAG順・2-SATを処理する
- 一意な後続・サイクル・ダブリング — 水色(導入)
- 関数グラフのcycle・tree分解 — 水色。概念上の親: 一意な後続・サイクル・ダブリング
- doubling・binary lifting — 水色。概念上の親: 一意な後続・サイクル・ダブリング
- cut・cycle性質から最適全域木を構成する — 水色
- Kruskal順の閾値DSU sweep — 青色。概念上の親: cut・cycle性質から最適全域木を構成する
- lowlinkで橋・関節点を特定する — 青色
- 次数parityからwalkや選択辺集合を判定・構成する — 水色(導入)
- Euler trail・circuit — 水色。概念上の親: 次数parityからwalkや選択辺集合を判定・構成する
- 指定次数parityの部分グラフ構成 — 青色。概念上の親: 次数parityからwalkや選択辺集合を判定・構成する
- フロー・マッチング・カットへ帰着する — 青色(導入)
- 二部matching・Hall・Kőnig — 青色。概念上の親: フロー・マッチング・カットへ帰着する
- 最大流・最小カット — 青色。概念上の親: フロー・マッチング・カットへ帰着する
- 閉路数・次数構造からgraph coreを調べる — 水色(導入)
- 単一サイクル成分とgraph core — 水色。概念上の親: 閉路数・次数構造からgraph coreを調べる
- cycle space・fundamental cycle basis — 青色
- 単調path contraction・DSU jump — 青色
- near-tree graphのkernel化 — 黄色
- 有向walkの周期・cycle差分gcd — 黄色
- 下限制約付きflowの実現可能性 — 黄色。概念上の親: フロー・マッチング・カットへ帰着する
- 最小費用流・circulation — 黄色。概念上の親: フロー・マッチング・カットへ帰着する
- 重み付き二部完全matching — 黄色。概念上の親: フロー・マッチング・カットへ帰着する
- 平面graph双対・cut/path対応 — 黄色
- path matchingのheap縮約greedy — 橙色
- 一般グラフの最小重み完全matching — 赤色
問題一覧
この単元に直接配置する問題はありません。下位単元または関連問題を参照してください。
各問題の解説は問題ごとの本文として執筆します。各項目には主題・追加で学ぶ技能・既習技能の役割を示します。
関連問題
他の主題と組み合わせる問題を読む
以下はこのUnitのOutcomeを追加で学ぶ技能または既習技能として参照する、別のUnitを主題とする問題です。
- ABC218 F「Blocked Roads」 公式問題
技能・出典
主題: 基準witnessから変更影響を局所化する(基準となる解や経路を証拠に、答えが変わり得る変更だけを特定して再計算を局所化できる。)。追加で学ぶ技能: 最短路を証明する木・経路の復元(距離等式を満たす親辺を選び、最短路の木または経路を復元できる。)。既習技能: 最短路モデル(非負重みの距離確定を証明し、一般非負重みでは優先度付きキュー、0・1重みではdeque、単位重みではFIFOを選べる。)。主タグ: 最短路を証明する木・経路の復元、基準解による変更影響の局所化 / 補助タグ: 最短路モデル
- ABC224 E「Integers on Grid」 公式問題
技能・出典
主題: DP遷移を因数分解・集約して加速する(遷移式を属性別極値・少数の重み付き和へ分解し、その集計値が更新について閉じることを示せる。)。既習技能: event順にactive集合を更新する(値・時刻・座標順にeventを並べ、同値eventの処理順とactive集合の増分更新を設計できる。) / DAGのtopological processing(依存辺の向きを定め、入次数またはpostorderからtopological順を作って制約伝播・DP・scheduleを処理する。その発動条件、正当性、計算量を説明し、未知問へ実装できる。)。 dp_i=1+max_{a_j>a_i,同じ行または列}dp_j型の遷移を行別・列別最大へ圧縮する。遷移先がなければ0。同値のbatchでは全取得を済ませてから更新し、狭義不等号を保つ。sort後の集約はO(N)。主タグ: DP遷移の集約・高速化 / 補助タグ: DAGのtopological processing、event・値順のオフライン走査
- ABC229 E「Graph Destruction」 公式問題主題: 時間を逆向きにして未来依存を消す
技能・出典
主題: 時間を逆向きにして未来依存を消す(時間依存を逆走査・逆操作・last-write時刻で単調または静的にし、元の時点へ答えを戻せる。)。既習技能: DSUによる連結成分管理・縮約(静的な辺を探索して成分を付けるか、辺追加ごとに成分を併合し、同一成分・サイズを判定できる。)。主タグ: 逆向きのオフライン処理 / 補助タグ: DSUによる連結成分管理・縮約
- ABC233 F「Swap and Sort」 公式問題主題: 成立証明から構成解を復元する
技能・出典
主題: 成立証明から構成解を復元する(成立証明に対応する親・局所操作・選択を記録し、要件を満たす構成を出力できる。)。既習技能: DSUによる連結成分管理・縮約(静的な辺を探索して成分を付けるか、辺追加ごとに成分を併合し、同一成分・サイズを判定できる。)。主タグ: 構成解・witness復元 / 補助タグ: DSUによる連結成分管理・縮約
- ABC237 Ex「Hakata」 公式問題
技能・出典
主題: 半順序・Dilworth・最大反鎖(対象を半順序へ写し、Dilworth型のchain/antichain双対をLDS・matching・min-cutの適切な形で解ける。)。既習技能: 二部matching・Hall・Kőnig(左右の一対一割当をaugmenting pathまたは単位容量flowで解き、Hall条件・Kőnigの定理・path coverへ接続する。その発動条件、正当性、計算量を説明し、未知問へ実装できる。)。主タグ: 半順序・Dilworth・最大反鎖 / 補助タグ: 二部matching・Hall・Kőnig
- ABC239 F「Construct Highway」 公式問題主題: 成立証明から構成解を復元する
技能・出典
主題: 成立証明から構成解を復元する(成立証明に対応する親・局所操作・選択を記録し、要件を満たす構成を出力できる。)。既習技能: DSUによる連結成分管理・縮約(静的な辺を探索して成分を付けるか、辺追加ごとに成分を併合し、同一成分・サイズを判定できる。)。主タグ: 構成解・witness復元 / 補助タグ: DSUによる連結成分管理・縮約
- ABC257 G「Prefix Concatenation」 公式問題
技能・出典
主題: Z algorithmによるprefix matching(既知のZ-boxを再利用してZ arrayを線形時間で構成し、各位置から始まる接尾辞と文字列全体のprefixの最大一致長を、文字列連結によるprefix照合へ利用できる。)。既習技能: 状態グラフのモデリングと探索(暗黙状態・重みなし辺・訪問条件を定義し、到達判定・最短手数・列挙の目的に応じてBFS・DFS・backtrackingを選べる。)。主タグ: Z algorithmによるprefix matching / 補助タグ: 状態グラフのモデリングと探索
- ABC258 E「Packing Potatoes」 公式問題
技能・出典
主題: 尺取り法・sliding windowで連続区間を走査する(一列の窓または二列の現在blockに関する不変条件を保ち、各pointerを単調に進められる。)。既習技能: 関数グラフのcycle・tree分解(後続が一意なグラフをcycleと流入木へ分け、各頂点が属する構造を特定できる。)。主タグ: 尺取り法・sliding window / 補助タグ: 関数グラフのcycle・tree分解
- ABC261 G「Replace」 公式問題主題: 区間合成・領域分割DP
技能・出典
主題: 区間合成・領域分割DP(区間や長方形の分割点を列挙し、独立な小領域の答えを合成して領域サイズ順に計算できる。)。既習技能: 最短路モデル(非負重みの距離確定を証明し、一般非負重みでは優先度付きキュー、0・1重みではdeque、単位重みではFIFOを選べる。)。主タグ: 区間合成・領域分割DP / 補助タグ: 最短路モデル
- ABC264 E「Blackout 2」 公式問題主題: 時間を逆向きにして未来依存を消す
技能・出典
主題: 時間を逆向きにして未来依存を消す(時間依存を逆走査・逆操作・last-write時刻で単調または静的にし、元の時点へ答えを戻せる。)。既習技能: DSUによる連結成分管理・縮約(成分へmetadataまたはmerge履歴を集約し、成分を一頂点に縮約した隣接関係、または併合後の代表情報を構成できる。)。主タグ: 逆向きのオフライン処理 / 補助タグ: DSUによる連結成分管理・縮約
- ABC264 G「String Fair」 公式問題主題: 有限状態automatonの構成
技能・出典
主題: 有限状態automatonの構成(未来の一文字遷移を決める有限同値類を定義し、pattern suffix・subsequence進行・圧縮DP rowなどから完全遷移表を構成してDPや行列累乗に接続できる。)。追加で学ぶ技能: 最短路モデル(辺数を制限した反復緩和から負閉路・正閉路の検出を導き、始点到達性と終点への影響を区別できる。)。主タグ: 有限状態automatonの構成、最短路モデル
- ABC297 E「Kth Takoyaki Set」 公式問題
技能・出典
主題: priority queue・best-first列挙(現在のfrontierの極値をheapで確定し、新しく解禁された候補だけを追加して上位K個や最良状態を列挙する。その発動条件、正当性、計算量を説明し、未知問へ実装できる。)。既習技能: 最短路モデル(非負重みの距離確定を証明し、一般非負重みでは優先度付きキュー、0・1重みではdeque、単位重みではFIFOを選べる。)。主タグ: priority queue・best-first列挙 / 補助タグ: 最短路モデル
- ABC299 E「Nearest Black Vertex」 公式問題主題: 成立証明から構成解を復元する
技能・出典
主題: 成立証明から構成解を復元する(成立証明に対応する親・局所操作・選択を記録し、要件を満たす構成を出力できる。)。既習技能: 最短路モデル(非負重みの距離確定を証明し、一般非負重みでは優先度付きキュー、0・1重みではdeque、単位重みではFIFOを選べる。)。主タグ: 構成解・witness復元 / 補助タグ: 最短路モデル
- ABC301 E「Pac-Takahashi」 公式問題主題: 部分集合・bitmask状態DP
技能・出典
主題: 部分集合・bitmask状態DP(bitmaskの各bitが表す意味を定め、部分集合間の遷移を正しく設計できる。)。既習技能: 最短路モデル(非負重みの距離確定を証明し、一般非負重みでは優先度付きキュー、0・1重みではdeque、単位重みではFIFOを選べる。)。 BFSで重要地点間の距離を前計算し、移動の全履歴を距離へ圧縮する。その上でdp[S][v]から未訪問の代表地点へ進む部分集合DPを学び、最後に出口への距離を加えて時間制約を判定する。通過した菓子を全て状態に記録しなくても最適値を失わない理由も確かめる。主タグ: 部分集合・bitmask状態DP / 補助タグ: 最短路モデル
- ABC302 Ex「Ball Collector」 公式問題
技能・出典
主題: rollback・DFS入退場の状態復元(更新前の差分をstackへ記録し、分割統治・時間Segment Tree・DFSの退場時に状態を正確に巻き戻す。その発動条件、正当性、計算量を説明し、未知問へ実装できる。)。既習技能: DSUによる連結成分管理・縮約(成分へmetadataまたはmerge履歴を集約し、成分を一頂点に縮約した隣接関係、または併合後の代表情報を構成できる。)。主タグ: rollback・DFS入退場の状態復元 / 補助タグ: DSUによる連結成分管理・縮約
- ABC304 Ex「Constrained Topological Sort」 公式問題主題: 交換論から選択順を導く
技能・出典
主題: 交換論から選択順を導く(局所選択の交換または候補の支配関係を示し、安全な順序・候補・caseを確定できる。)。既習技能: DAGのtopological processing(依存辺の向きを定め、入次数またはpostorderからtopological順を作って制約伝播・DP・scheduleを処理する。その発動条件、正当性、計算量を説明し、未知問へ実装できる。)。主タグ: 貪欲法と交換論 / 補助タグ: DAGのtopological processing
- ABC305 E「Art Gallery on Graph」 公式問題
技能・出典
主題: priority queue・best-first列挙(現在のfrontierの極値をheapで確定し、新しく解禁された候補だけを追加して上位K個や最良状態を列挙する。その発動条件、正当性、計算量を説明し、未知問へ実装できる。)。既習技能: 最短路モデル(非負重みの距離確定を証明し、一般非負重みでは優先度付きキュー、0・1重みではdeque、単位重みではFIFOを選べる。)。主タグ: priority queue・best-first列挙 / 補助タグ: 最短路モデル
- ABC306 Ex「Balance Scale」 公式問題
技能・出典
主題: 包除・Möbius反転で重複を補正する(条件集合の重なり構造を特定し、包除またはMöbius反転の符号と範囲を正しく設定できる。)。既習技能: 部分集合・bitmask状態DP(bitmaskの各bitが表す意味を定め、部分集合間の遷移を正しく設計できる。) / DAGのtopological processing(依存辺の向きを定め、入次数またはpostorderからtopological順を作って制約伝播・DP・scheduleを処理する。その発動条件、正当性、計算量を説明し、未知問へ実装できる。)。主タグ: 集合上の包除原理 / 補助タグ: DAGのtopological processing、部分集合・bitmask状態DP
- ABC311 G「One More Grid Task」 公式問題
技能・出典
主題: event順にactive集合を更新する(値・時刻・座標順にeventを並べ、同値eventの処理順とactive集合の増分更新を設計できる。)。既習技能: 一次元・二次元累積和と差分で区間情報を線形化する(prefix配列またはprefix変数を置き、区間和を二つのprefix値の差で表現できる。多次元の直方体は2^D隅の包除で取得し、一括加算は端点差分へ変換できる。) / DSUによる連結成分管理・縮約(静的な辺を探索して成分を付けるか、辺追加ごとに成分を併合し、同一成分・サイズを判定できる。)。主タグ: event・値順のオフライン走査 / 補助タグ: DSUによる連結成分管理・縮約、累積和・差分配列
- ABC313 Ex「Group Photo」 公式問題主題: 最小十分状態からDPを設計する
技能・出典
主題: 最小十分状態からDPを設計する(採用解法の未来を決める最小十分状態と、捨てられる履歴を説明できる。)。既習技能: 二部matching・Hall・Kőnig(二部割当が可能であることを近傍集合の大きさに関するHall条件で特徴付け、必要ならmin-cut条件と対応させられる。) / 組合せ係数と対称性で数える(選択・順列・分配の重複の有無を識別し、組合せ係数の式を立てられる。)。主タグ: DPの最小十分状態 / 補助タグ: 二部matching・Hall・Kőnig、組合せ係数・数え上げ
- ABC314 F「A Certain Game」 公式問題
技能・出典
主題: DSU merge tree・Kruskal reconstruction tree(成分併合ごとに新しい親nodeを作り、併合時刻・threshold・成分包含を一つのrooted treeへ記録する。その発動条件、正当性、計算量を説明し、未知問へ実装できる。)。既習技能: 根付き木DP・部分木集約(根付き木で子側の状態を合成し、部分木または木全体の値を求められる。) / DSUによる連結成分管理・縮約(成分へmetadataまたはmerge履歴を集約し、成分を一頂点に縮約した隣接関係、または併合後の代表情報を構成できる。) / 法上の四則演算・高速累乗・逆元(剰余を正規化して加減乗算し、二分累乗と可逆性を確認した逆元により法上の除算・確率を計算できる。) / 局所寄与へ分解して集計順を交換する(数える対象を要素・組・値・区間のいずれかで一意に固定し、各対象が含まれる回数または指示変数の期待値を先に求めて総和できる。)。主タグ: DSU merge tree・Kruskal reconstruction tree / 補助タグ: 寄与の数え上げと順序交換、DSUによる連結成分管理・縮約、法上の四則演算・高速累乗・逆元、根付き木DP・部分木集約
- ABC318 F「Octopus」 公式問題主題: 整数境界と同値区間を正確に分ける
技能・出典
主題: 整数境界と同値区間を正確に分ける(成立判定が変わり得る整数境界を全て列挙し、隣り合う境界の間で判定が一定であることを示して、代表点判定と区間長で整数解の個数を求められる。)。既習技能: 二部matching・Hall・Kőnig(二部割当が可能であることを近傍集合の大きさに関するHall条件で特徴付け、必要ならmin-cut条件と対応させられる。) / 交換論から選択順を導く(局所選択の交換または候補の支配関係を示し、安全な順序・候補・caseを確定できる。)。主タグ: 整数境界・同値区間分割 / 補助タグ: 二部matching・Hall・Kőnig、貪欲法と交換論
- ABC324 F「Beautiful Path」 公式問題
技能・出典
主題: fractional programming・比率parametric search(比率候補xをbenefit-x·costの加法目的へ変換し、単調な判定問題を解いて最適比率を求められる。)。既習技能: DAGのtopological processing(依存辺の向きを定め、入次数またはpostorderからtopological順を作って制約伝播・DP・scheduleを処理する。その発動条件、正当性、計算量を説明し、未知問へ実装できる。) / 単調境界を証明して探索する(判定の単調性を証明し、二分探索の成功側・失敗側を設定できる。)。主タグ: fractional programming・比率parametric search / 補助タグ: DAGのtopological processing、単調境界探索
- ABC327 G「Many Good Tuple Problems」 公式問題
技能・出典
主題: label付き連結成分分解・exponential formula(最小labelを含む成分を一意に切り出し、全構造とconnected構造の関係をsubset DPまたは指数型母関数で解ける。)。既習技能: 二部彩色と成分構造を扱う(連結二部グラフの二つの彩色が部の交換だけで対応することを使い、彩色付きの計数から同じグラフの重複を補正できる。) / 法上の四則演算・高速累乗・逆元(剰余を正規化して加減乗算し、二分累乗と可逆性を確認した逆元により法上の除算・確率を計算できる。) / 包除・Möbius反転で重複を補正する(条件集合の重なり構造を特定し、包除またはMöbius反転の符号と範囲を正しく設定できる。) / 組合せ係数と対称性で数える(選択・順列・分配の重複の有無を識別し、組合せ係数の式を立てられる。)。主タグ: label付き連結成分分解・exponential formula / 補助タグ: 二部グラフの彩色と成分構造、組合せ係数・数え上げ、集合上の包除原理、法上の四則演算・高速累乗・逆元
- ABC328 E「Modulo MST」 公式問題
技能・出典
主題: 候補数を界して全列挙・有限case分解する(制約・生成パラメータ・固定選択数・有限caseから候補総数を界し、漏れなく全候補を生成・評価できる。)。既習技能: DSUによる連結成分管理・縮約(静的な辺を探索して成分を付けるか、辺追加ごとに成分を併合し、同一成分・サイズを判定できる。)。主タグ: 有界全列挙・有限case分解 / 補助タグ: DSUによる連結成分管理・縮約
- ABC336 F「Rotation Puzzle」 公式問題
技能・出典
主題: meet-in-the-middle・半分全列挙(探索空間を独立に列挙できる二集合へ分け、両側の結果を照合・合成できる。)。既習技能: 状態グラフのモデリングと探索(暗黙状態・重みなし辺・訪問条件を定義し、到達判定・最短手数・列挙の目的に応じてBFS・DFS・backtrackingを選べる。)。主タグ: meet-in-the-middle・半分全列挙 / 補助タグ: 状態グラフのモデリングと探索
- ABC336 G「16 Integers」 公式問題
技能・出典
主題: BEST定理によるEuler circuit数え上げ(有向Euler graphのcircuit数をrooted arborescenceの行列式と各頂点の出辺順列へ分解して数える。その発動条件、正当性、計算量を説明し、未知問へ実装できる。)。既習技能: Euler trail・circuit(無向graphでは辺を持つ部分の連結性と奇数次数頂点数が0または2であることを調べ、有向graphでは辺を持つ部分の弱連結性と入次数・出次数の差(trailなら始点+1、終点−1、他0、circuitなら全頂点0)を調べ、全辺を一度ずつ使うtrail・circuitの存在を判定できる。) / 法上の四則演算・高速累乗・逆元(剰余を正規化して加減乗算し、二分累乗と可逆性を確認した逆元により法上の除算・確率を計算できる。) / 行列式による数え上げ(辺重みからLaplacianを構成し、根の行列余因子を全域木の重み付き個数へ対応させられる。有向木の向きと自己ループの扱いを説明できる。) / 組合せ係数と対称性で数える(選択・順列・分配の重複の有無を識別し、組合せ係数の式を立てられる。)。主タグ: BEST定理によるEuler circuit数え上げ / 補助タグ: 組合せ係数・数え上げ、行列式による数え上げ、Euler trail・circuit、法上の四則演算・高速累乗・逆元
- ABC338 F「Negative Traveling Salesman」 公式問題主題: 部分集合・bitmask状態DP
技能・出典
主題: 部分集合・bitmask状態DP(bitmaskの各bitが表す意味を定め、部分集合間の遷移を正しく設計できる。)。既習技能: 最短路モデル(許す中継点集合を状態とするDPからFloyd–Warshallを導き、距離行列の更新順・到達不能・負閉路を扱える。)。 Floyd–Warshallで全点対距離を前計算し、最短路閉包上の訪問順を部分集合DPで学ぶ。maskは代表として訪問順へ追加した頂点集合であり、距離前計算の途中で通る頂点を禁止しない。任意のwalkから初訪問順を取り出す方向と、DP解をwalkへ展開する方向で同値性を示す。主タグ: 部分集合・bitmask状態DP / 補助タグ: 最短路モデル
- ABC341 F「Breakdown」 公式問題主題: 資源・容量DP
技能・出典
主題: 資源・容量DP(資源軸の上限と更新順を選び、選択の重複を避けられる。)。既習技能: DAGのtopological processing(依存辺の向きを定め、入次数またはpostorderからtopological順を作って制約伝播・DP・scheduleを処理する。その発動条件、正当性、計算量を説明し、未知問へ実装できる。)。主タグ: 資源軸knapsack DP / 補助タグ: DAGのtopological processing
- ABC349 G「Palindrome Construction」 公式問題主題: 回文半径と左右対称区間を特定する
技能・出典
主題: 回文半径と左右対称区間を特定する(各中心の回文半径を求め、左右対称な区間の成立条件を判定できる。)。既習技能: DSUによる連結成分管理・縮約(静的な辺を探索して成分を付けるか、辺追加ごとに成分を併合し、同一成分・サイズを判定できる。) / 成立証明から構成解を復元する(成立証明に対応する親・局所操作・選択を記録し、要件を満たす構成を出力できる。)。主タグ: 回文半径・Manacher / 補助タグ: 構成解・witness復元、DSUによる連結成分管理・縮約
- ABC352 F「Estimate Order」 公式問題主題: 部分集合・bitmask状態DP
技能・出典
主題: 部分集合・bitmask状態DP(bitmaskの各bitが表す意味を定め、部分集合間の遷移を正しく設計できる。)。既習技能: 静的graph等式制約のpotential伝播(辺等式をDFS/BFSでroot-relative potentialへ伝播し、cycle矛盾を検出して各連結成分の全解を自由offset一つで表現・復元できる。)。主タグ: 部分集合・bitmask状態DP / 補助タグ: 静的graph等式制約のpotential伝播
- ABC354 G「Select Strings」 公式問題
技能・出典
主題: 半順序・Dilworth・最大反鎖(対象を半順序へ写し、Dilworth型のchain/antichain双対をLDS・matching・min-cutの適切な形で解ける。)。既習技能: 最大流・最小カット(選択・排反・closure・頂点容量をcapacity networkへ写し、残余グラフとmax-flow min-cut定理から最適値とcut側を復元する。その発動条件、正当性、計算量を説明し、未知問へ実装できる。)。主タグ: 半順序・Dilworth・最大反鎖 / 補助タグ: 最大流・最小カット
- ABC363 G「Dynamic Scheduling」 公式問題
技能・出典
主題: rollback・DFS入退場の状態復元(更新前の差分をstackへ記録し、分割統治・時間Segment Tree・DFSの退場時に状態を正確に巻き戻す。その発動条件、正当性、計算量を説明し、未知問へ実装できる。)。既習技能: 二部matching・Hall・Kőnig(二部割当が可能であることを近傍集合の大きさに関するHall条件で特徴付け、必要ならmin-cut条件と対応させられる。) / Segment Treeのcanonical区間分解(区間をO(log N)個のcanonical nodeへ分解してrange object・時間生存区間・range edgeを配置し、point queryではroot-to-leaf path上のobjectを集められる。) / 区間更新を要約へ作用させる(更新作用の合成順と要約への適用を定義し、遅延評価で保てる。)。主タグ: rollback・DFS入退場の状態復元 / 補助タグ: 二部matching・Hall・Kőnig、遅延評価する区間作用、Segment Treeのcanonical区間分解
- ABC364 G「Last Major City」 公式問題
技能・出典
主題: Steiner tree subset DP(terminal subsetと終点を状態に、subset分割mergeとmulti-source shortest path relaxationを交互に行う。その発動条件、正当性、計算量を説明し、未知問へ実装できる。)。既習技能: 最短路モデル(非負重みの距離確定を証明し、一般非負重みでは優先度付きキュー、0・1重みではdeque、単位重みではFIFOを選べる。)。主タグ: Steiner tree subset DP / 補助タグ: 最短路モデル
- ABC369 E「Sightseeing Tour」 公式問題
技能・出典
主題: 候補数を界して全列挙・有限case分解する(制約・生成パラメータ・固定選択数・有限caseから候補総数を界し、漏れなく全候補を生成・評価できる。)。既習技能: 最短路モデル(許す中継点集合を状態とするDPからFloyd–Warshallを導き、距離行列の更新順・到達不能・負閉路を扱える。)。主タグ: 有界全列挙・有限case分解 / 補助タグ: 最短路モデル
- ABC370 F「Cake Division」 公式問題
技能・出典
主題: 尺取り法・sliding windowで連続区間を走査する(一列の窓または二列の現在blockに関する不変条件を保ち、各pointerを単調に進められる。)。既習技能: doubling・binary lifting(一意な遷移の2の冪回先を前計算し、巨大回数後の状態または区間到達を求められる。) / 単調境界を証明して探索する(判定の単調性を証明し、二分探索の成功側・失敗側を設定できる。)。主タグ: 尺取り法・sliding window / 補助タグ: doubling・binary lifting、単調境界探索
- ABC371 G「Lexicographically Smallest Permutation」 公式問題主題: 交換論から選択順を導く
技能・出典
主題: 交換論から選択順を導く(局所選択の交換または候補の支配関係を示し、安全な順序・候補・caseを確定できる。)。追加で学ぶ技能: 一次合同・CRTで解の類を統合する(合同条件の可解性を判定し、逆元・一次合同・CRTで解の類を構成できる。)。既習技能: 関数グラフのcycle・tree分解(後続が一意なグラフをcycleと流入木へ分け、各頂点が属する構造を特定できる。)。主タグ: 貪欲法と交換論、一次合同・CRT / 補助タグ: 関数グラフのcycle・tree分解
- ABC375 F「Road Blocked」 公式問題主題: 時間を逆向きにして未来依存を消す
技能・出典
主題: 時間を逆向きにして未来依存を消す(時間依存を逆走査・逆操作・last-write時刻で単調または静的にし、元の時点へ答えを戻せる。)。既習技能: 最短路モデル(許す中継点集合を状態とするDPからFloyd–Warshallを導き、距離行列の更新順・到達不能・負閉路を扱える。)。主タグ: 逆向きのオフライン処理 / 補助タグ: 最短路モデル
- ABC376 G「Treasure Hunting」 公式問題
技能・出典
主題: 01 on Tree・親先行順序のcluster縮約(親先行制約下の交換比較をcluster統計へまとめ、01 on Treeの縮約貪欲で最適順序を構成できる。)。既習技能: priority queue・best-first列挙(現在のfrontierの極値をheapで確定し、新しく解禁された候補だけを追加して上位K個や最良状態を列挙する。その発動条件、正当性、計算量を説明し、未知問へ実装できる。) / DSUによる連結成分管理・縮約(静的な辺を探索して成分を付けるか、辺追加ごとに成分を併合し、同一成分・サイズを判定できる。) / 交換論から選択順を導く(局所選択の交換または候補の支配関係を示し、安全な順序・候補・caseを確定できる。)。主タグ: 01 on Tree・親先行順序のcluster縮約 / 補助タグ: DSUによる連結成分管理・縮約、貪欲法と交換論、priority queue・best-first列挙
- ABC393 G「Unevenness」 公式問題
技能・出典
主題: Lagrangian relaxation・Aliens trick(個数制約へpenalty λを加えたoracleで双対下界を求める。厳密復元には個数別最適値の離散凸性などから対象個数で双対ギャップがないことを証明し、その上で個数単調性とtie-breakにより支持直線を探索する。その発動条件、正当性、計算量を説明し、未知問へ実装できる。)。既習技能: 連分数・Stern–Brocotで有理近似する(Euclid互除法・連分数・Stern–Brocotの区間を使い、分母上限下の最良有理近似を求められる。) / 最短路モデル(辺数を制限した反復緩和から負閉路・正閉路の検出を導き、始点到達性と終点への影響を区別できる。) / 最小費用流・circulation(流量と費用を持つ残余networkを設計し、potential付き最短路・slope・cycle cancelingで流量別最小費用を求める。その発動条件、正当性、計算量を説明し、未知問へ実装できる。)。主タグ: Lagrangian relaxation・Aliens trick / 補助タグ: 最小費用流・circulation、連分数・Stern–Brocot有理近似、最短路モデル
- ABC394 G「Dense Buildings」 公式問題
技能・出典
主題: parallel binary search・多数境界の判定共有(各queryの未確定区間を保ち、同じroundのmidをbucketして一方向更新できる判定器を共有し、全queryの最小・最大成立境界を求められる。)。既習技能: event順にactive集合を更新する(値・時刻・座標順にeventを並べ、同値eventの処理順とactive集合の増分更新を設計できる。) / DSUによる連結成分管理・縮約(静的な辺を探索して成分を付けるか、辺追加ごとに成分を併合し、同一成分・サイズを判定できる。) / 単調境界を証明して探索する(判定の単調性を証明し、二分探索の成功側・失敗側を設定できる。)。主タグ: parallel binary search・多数境界の判定共有 / 補助タグ: DSUによる連結成分管理・縮約、event・値順のオフライン走査、単調境界探索
- ABC395 G「Minimum Steiner Tree 2」 公式問題
技能・出典
主題: Steiner tree subset DP(terminal subsetと終点を状態に、subset分割mergeとmulti-source shortest path relaxationを交互に行う。その発動条件、正当性、計算量を説明し、未知問へ実装できる。)。既習技能: 最短路モデル(非負重みの距離確定を証明し、一般非負重みでは優先度付きキュー、0・1重みではdeque、単位重みではFIFOを選べる。)。主タグ: Steiner tree subset DP / 補助タグ: 最短路モデル
- ABC398 E「Tree Game」 公式問題
技能・出典
主題: 偶奇不変量からゲームの勝敗を決める(合法手が独立な固定候補の消費に限られる場合や、成分分類から残手数の偶奇を求められる場合に、勝敗を決める偶奇量と応答戦略を証明し、局面ごとのDPなしで勝者を判定できる。)。追加で学ぶ技能: 二部彩色と成分構造を扱う(各連結成分を二色に塗って矛盾を検出し、二つの部の大きさと色反転の自由度を成分ごとに集約できる。)。既習技能: 対話protocolを守って情報を取得する(judgeとの問い合わせ応答または交互手番のprotocolを守り、許された形式で応答依存の探索・合法手の提示・終了処理を実行できる。query上限がある場合はその回数も満たす。)。主タグ: 二部グラフの彩色と成分構造、偶奇不変量によるゲーム戦略 / 補助タグ: 対話protocolとquery設計
- ABC398 G「Not Only Tree Game」 公式問題
技能・出典
主題: 偶奇不変量からゲームの勝敗を決める(合法手が独立な固定候補の消費に限られる場合や、成分分類から残手数の偶奇を求められる場合に、勝敗を決める偶奇量と応答戦略を証明し、局面ごとのDPなしで勝者を判定できる。)。追加で学ぶ技能: 二部彩色と成分構造を扱う(各連結成分を二色に塗って矛盾を検出し、二つの部の大きさと色反転の自由度を成分ごとに集約できる。)。 - ABC408 E「Minimum OR Path」 公式問題
技能・出典
主題: bitwise greedyによるmask最適化(上位bitから候補maskを仮定し、残り問題のfeasibility oracleでそのbitを保持/除去できるか決める。その発動条件、正当性、計算量を説明し、未知問へ実装できる。)。既習技能: DSUによる連結成分管理・縮約(静的な辺を探索して成分を付けるか、辺追加ごとに成分を併合し、同一成分・サイズを判定できる。) / 交換論から選択順を導く(局所選択の交換または候補の支配関係を示し、安全な順序・候補・caseを確定できる。)。主タグ: bitwise greedyによるmask最適化 / 補助タグ: DSUによる連結成分管理・縮約、貪欲法と交換論
- ABC409 F「Connecting Points」 公式問題
技能・出典
主題: priority queue・best-first列挙(現在のfrontierの極値をheapで確定し、新しく解禁された候補だけを追加して上位K個や最良状態を列挙する。その発動条件、正当性、計算量を説明し、未知問へ実装できる。)。既習技能: 候補数を界して全列挙・有限case分解する(制約・生成パラメータ・固定選択数・有限caseから候補総数を界し、漏れなく全候補を生成・評価できる。) / DSUによる連結成分管理・縮約(静的な辺を探索して成分を付けるか、辺追加ごとに成分を併合し、同一成分・サイズを判定できる。)。主タグ: priority queue・best-first列挙 / 補助タグ: 有界全列挙・有限case分解、DSUによる連結成分管理・縮約
- ABC413 F「No Passage」 公式問題
技能・出典
主題: 循環局面の後退解析とminimax距離(終了局面から逆辺を辿り、終了側が一手選べば確定するOR局面と全手の確定を待つAND局面を区別する。未確定局面で無限継続を判定し、非負重みなら優先度付きキューで有限なminimax距離を確定する。その発動条件、正当性、計算量を説明し、未知問へ実装できる。)。既習技能: 状態グラフのモデリングと探索(暗黙状態・重みなし辺・訪問条件を定義し、到達判定・最短手数・列挙の目的に応じてBFS・DFS・backtrackingを選べる。)。主タグ: 循環局面の後退解析とminimax距離 / 補助タグ: 状態グラフのモデリングと探索
- ABC417 E「A Path in A Dictionary」 公式問題主題: 交換論から選択順を導く
技能・出典
主題: 交換論から選択順を導く(局所選択の交換または候補の支配関係を示し、安全な順序・候補・caseを確定できる。)。既習技能: 状態グラフのモデリングと探索(暗黙状態・重みなし辺・訪問条件を定義し、到達判定・最短手数・列挙の目的に応じてBFS・DFS・backtrackingを選べる。)。主タグ: 貪欲法と交換論 / 補助タグ: 状態グラフのモデリングと探索
- ABC417 G「Binary Cat」 公式問題
技能・出典
主題: 圧縮・反復・再帰文字列へ問い合わせる(圧縮・反復・再帰または入れ子で定義された文字列を展開せず、block長・対応区切り・作用から照会・変換・評価できる。)。既習技能: 単調進行による償却解析(要素の一方向移動・一度だけの削除・軽辺へ進むたびの部分問題サイズ半減など、単調に減るpotentialから操作列全体の仕事量を抑えられる。) / doubling・binary lifting(一意な遷移の2の冪回先を前計算し、巨大回数後の状態または区間到達を求められる。)。主タグ: 再帰・圧縮・入れ子文字列の走査 / 補助タグ: 単調進行による償却解析、doubling・binary lifting
- ABC424 G「Set list」 公式問題主題: 資源・容量DP
技能・出典
主題: 資源・容量DP(資源軸の上限と更新順を選び、選択の重複を避けられる。)。既習技能: 二部matching・Hall・Kőnig(二部割当が可能であることを近傍集合の大きさに関するHall条件で特徴付け、必要ならmin-cut条件と対応させられる。)。主タグ: 資源軸knapsack DP / 補助タグ: 二部matching・Hall・Kőnig
- ABC429 F「Shortest Path Query」 公式問題主題: 区間monoid要約
技能・出典
主題: 区間monoid要約(要約する値・単位元・結合的な合成規則を定義し、prefix fold・Segment Tree・SWAGで答えを求められる。)。既習技能: 半環行列・min-plus/max-min遷移(遷移を半環行列として定義し、結合則と単位元を保つ二分累乗・区間積で巨大回数の最適化遷移を計算できる。) / 最短路モデル(DAGや使用可能な辺列の順に緩和し、処理済みprefixが表す経路集合を不変量として説明できる。)。主タグ: 区間monoid要約 / 補助タグ: 半環行列・min-plus/max-min遷移、最短路モデル
- ABC440 G「Haunted House」 公式問題主題: 最小十分状態からDPを設計する
技能・出典
主題: 最小十分状態からDPを設計する(採用解法の未来を決める最小十分状態と、捨てられる履歴を説明できる。)。既習技能: DSUによる連結成分管理・縮約(成分へmetadataまたはmerge履歴を集約し、成分を一頂点に縮約した隣接関係、または併合後の代表情報を構成できる。)。主タグ: DPの最小十分状態 / 補助タグ: DSUによる連結成分管理・縮約
- ABC444 G「Kyoen」 公式問題主題: Gaussian整数・二平方和
技能・出典
主題: Gaussian整数・二平方和(Z[i]での素因数分解と共役を用い、整数の二平方和表現をprime exponentごとに構成・数え上げる。その発動条件、正当性、計算量を説明し、未知問へ実装できる。)。既習技能: 関数グラフのcycle・tree分解(後続が一意なグラフをcycleと流入木へ分け、各頂点が属する構造を特定できる。)。主タグ: Gaussian整数・二平方和 / 補助タグ: 関数グラフのcycle・tree分解
- ABC447 E「Divide Graph」 公式問題主題: 交換論から選択順を導く
技能・出典
主題: 交換論から選択順を導く(局所選択の交換または候補の支配関係を示し、安全な順序・候補・caseを確定できる。)。既習技能: DSUによる連結成分管理・縮約(静的な辺を探索して成分を付けるか、辺追加ごとに成分を併合し、同一成分・サイズを判定できる。)。主タグ: 貪欲法と交換論 / 補助タグ: DSUによる連結成分管理・縮約
- ABC451 G「Minimum XOR Walk」 公式問題主題: XOR線形基底
技能・出典
主題: XOR線形基底(XOR部分空間の基底をpivot bitごとにreduced formへ整え、高位bitから基底を加減してaffine cosetの最小整数代表を一意に得る。正規化写像の線形性を示し、二値のXOR最小化を各値の正規化へ分離できる。)。既習技能: cycle space・fundamental cycle basis(spanning treeのroot-to-vertex XOR potentialで辺ラベルをfundamental cycleのXORへ変換し、cycle spaceの線形像が非木辺ごとのcycle XORのspanと一致することを示して、walkへ挿入できるXOR値をbasisで表せる。) / bit列をTrieで索引化する(整数を上位bitからTrieへ格納し、部分木情報を保ちながらXOR・大小条件に最適な分岐を選べる。)。主タグ: XOR線形基底 / 補助タグ: binary Trieによるbit列索引、cycle space・fundamental cycle basis
- ABC454 E「LRUD Moving」 公式問題主題: 成立証明から構成解を復元する
技能・出典
主題: 成立証明から構成解を復元する(成立証明に対応する親・局所操作・選択を記録し、要件を満たす構成を出力できる。)。既習技能: 二部彩色と成分構造を扱う(各連結成分を二色に塗って矛盾を検出し、二つの部の大きさと色反転の自由度を成分ごとに集約できる。)。主タグ: 構成解・witness復元 / 補助タグ: 二部グラフの彩色と成分構造
- ABC466 G「Segment Sum Constraints」 公式問題
技能・出典
主題: 繰り上がり・借り・混合基数を状態にするDP(整除鎖の端数または加算式を下位桁から処理し、切り上げ・切り下げや次桁へのcarryだけを状態にした遷移を設計できる。)。追加で学ぶ技能: potential・weighted DSU(DSUの親辺にpotential差を持たせ、経路圧縮時の差の累積と根の併合方向に応じた符号を導出し、オンラインの差制約追加と頂点間差・矛盾のqueryを処理できる。)。
前提・学習成果・出典
導入対象の目安: 緑色(800–1199)。状態と遷移を頂点と辺で表し、距離・連結性・向きの違いを整理する入口。
対象色の読み方は本書の読み方を参照してください。
Canonical taxonomy: FinalTaxonomyBuild final-taxonomy-build-initial digest f1ae39bc7201c3374c108e800284e1e0068ce6f7a57f15b2a9e5219616e3c4fe / LearningUnit unit-chapter-graph
習得する技能
- 対象を頂点と辺に対応させ、利用するグラフ性質を示せる。
前提と範囲
共通前提: prereq-abc-advanced-v1 (1.0.0)。
直接の前提単元: なし。
このUnitを直接前提とする単元: なし。
対象を頂点と辺へ写して到達可能性を扱えるようにし、連結性・最短路・木・フローへ進む土台を作る。
このUnitでは扱わないもの
- なし