了解です。
以下では定義 → 等価性 → 競プロ上の意味の順で、余分な比喩なしに説明します。
1. グラフ ＝ 状態遷移
定義
- 状態：問題の進行状況を完全に記述する情報
- 遷移：1 回の操作で状態が別の状態に変わること
等価性の理由
任意の計算過程は
[
\text{状態} \xrightarrow{\text{操作}} \text{次の状態}
]
という写像の列として表現できる。
これを形式化すると：
- 各状態を 頂点
- 各操作可能性を 有向辺
とする 有向グラフ が一意に定まる。
逆に、有向グラフ上のパスは
「初期状態から操作列を適用した結果」
を完全に表している。
したがって
状態空間＋遷移規則 ≡ 有向グラフ
これは単なる比喩ではなく、計算モデルとして同型。
競プロ上の意味
- BFS / DFS / Dijkstra を「グラフ問題」と見ている時点で負け
- 実際には
「状態設計が問題の 9 割」 - グラフは 描くもの ではなく 暗黙に定義されているもの
2. DP ＝ 半順序上の最短路
定義
-
DP：
[
dp[x] = \min_{y \in \text{pre}(x)} (dp[y] + cost(y \to x))
] -
半順序（poset）：
- 反射律・推移律はある
- 反対称性はあるが、全順序ではない
等価性の理由
DP が成立するための本質条件は 2 つだけ：
- 循環がない（自己参照しない）
- 各状態は「前の状態」からのみ更新される
これはそのまま：
- 状態集合：頂点
- 遷移方向：半順序の向き
- 重み：遷移コスト
とした DAG 上の最短路問題。
DP の更新順は、
- トポロジカル順序を一つ選んでいるだけ
よって：
DP ≡ 半順序で整列された DAG 上の最短路
「DP は配列を埋めるもの」という理解は実装レベルの話。
競プロ上の意味
- 「DP に見えない DP」は
半順序を見抜けていないだけ - 区間 DP / bit DP / 桁 DP も
全て「半順序の取り方」が違うだけ
3. 貪欲 ＝ マトロイド / 交換法
定義
-
貪欲：局所的に最良な選択を積み重ねる
-
マトロイド：
集合族 ( \mathcal{I} ) が- 空集合を含む
- 遺伝的（部分集合も可）
- 交換公理を満たす
等価性の理由
貪欲が常に正解になるためには：
- 「早く選んだ要素が、後の最適性を壊さない」
必要がある。
これを厳密に保証する条件が 交換公理：
任意の 2 つの独立集合 (A, B)（|A| < |B|）について
(B \setminus A) の要素で (A) に追加できるものが存在する
この性質があると：
- 「重み最大の要素から順に取る」
という貪欲戦略が 必ず最適解に到達することが証明できる。
逆に、
- この構造がない問題で貪欲が成功することはない。
したがって：
貪欲法が正しい ⇔ 問題構造がマトロイド的
競プロで言う「交換法」は、
この公理を問題ごとに手書きで証明しているに過ぎない。
競プロ上の意味
- 貪欲は「発想」ではない
- 構造判定問題
- 証明が苦しい貪欲は、ほぼ例外なく構造を誤認している
全体の統一視点
| 表現 | 実体 |
|---|---|
| グラフ | 状態空間と遷移 |
| DP | 半順序付き DAG の最短路 |
| 貪欲 | マトロイド上の最適化 |
青 perf 初見勢はこれを
- 名前としてではなく
- 同一物の別表現として扱っている
だから「初見」に見えるだけで、
実際には 既知構造への即時写像をしている、というわけです。
リンク