静的graph等式制約のpotential伝播
概要
辺が「片方の頂点値が決まれば、もう片方も決まる」という等式を表すとき、一つの根からDFS・BFSで値を伝播できる。別の経路から同じ頂点へ来たときも同じ値になるかを調べれば、全制約が両立するか分かる。
扱う等式は の形で、 は頂点の値、 は辺の重みである。 は、この単元では加法 またはビットごとの排他的論理和(XOR) を表す。加法なら 、XORなら と同じ意味になる。
根の値を仮に0として求めた相対値をポテンシャル と呼ぶ。実際の根の値はまだ自由で、その値を成分全体へ反映する共通の調整値を offset と呼ぶ。加法では全頂点に を足し、XORでは全頂点に をXORする。この自由度を残しておくと、等式を満たすかの判定と、解の最適化を分けて考えられる。
考え方
加法:根からの差を足し上げる
三頂点の独自例として、次の制約を考える。
頂点1を根にして と置く。辺 から 、辺 から と決まる。残る辺 でも なので一致する。未訪問の頂点では値を割り当て、訪問済みの頂点では既存の値と照合する、という操作で全辺を検査すればよい。
逆向きには なので、重み の辺 に対し、逆辺 の重みは にする。この例の閉路 の和は である。最後の制約だけを に変えると、頂点3への二経路が5と6を要求し、閉路和も となる。このとき等式系に解はない。
整合する例の全解は である。根の値を に変えると、どの頂点も同じだけ平行移動する。同じ成分内の差は変わらない。
XOR:根からのXORを累積する
今度は、同じ三頂点に次の制約を置く。
XORは同じ値を二度適用すると打ち消し合う。従って の逆向きも であり、逆辺の重みは符号を変えず のままにする。
から伝播すると 、 となる。直接の辺 でも と一致し、閉路のXORは になる。最後の制約だけを に変えると、頂点3の値が二経路で1と0に分かれ、閉路XORも1となって解がなくなる。
整合する例の全解は である。例えば なら となる。加法の平行移動とは異なり、 の立っているbitを全頂点で反転する操作になる。
各成分に残る自由度を取り出す
どちらの演算でも、未訪問の根を選ぶたびに0を置き、成分内の頂点を探索する。割当て時に訪問済みと記録し、探索中に出会う全ての辺で等式を照合する。ここでのBFSは最短距離を求めるためではなく、等式を伝えるための探索である。
検査に通ったなら、加法では 、XORでは とすれば、共通の が差やXORから打ち消されて全辺の等式を満たす。逆に、どの解も根の値 を決めれば辺の伝播で全頂点の値が決まるので、この形で全解を表せる。照合に失敗した辺があれば、どの を選んでも二経路の不一致は解消しない。
別の連結成分との間には辺がないので、成分ごとに独立した を選べる。孤立点も一頂点の成分として扱う。値の範囲や総和最小化などの追加条件がある場合は、この残った自由度へ条件を課す。
成立条件と計算量
前提は、辺が加法またはXORの等式を指定し、逆向きにも一意に値を戻せること。両者で検査する条件と全解の形を混ぜない。
| 確認するもの | 加法 | XOR |
|---|---|---|
| 逆辺の重み | ||
| 閉路の整合条件 | 重みの和が0 | 重みのXORが0 |
| 頂点値の全解 |
自己ループや多重辺も検査対象になる。加法の累積値は一つの辺重みより大きくなりうるため、経路全体の和が収まる整数型を用意する。XORでは入力の重みを表せるbit幅を確保する。一回の演算を定数時間とすると、 頂点 辺の隣接リストの構築と伝播は、全成分を合わせて時間・空間ともに 。成分ごとの最適化に必要な計算量は別に評価する。
大小の不等式では、一方の値を決めても他方は一意に決まらないので、この伝播だけでは解けない。また、追加条件まで自動で満たせるわけではない。ABC396 Eの解説では共通XORの各bitを選んで総和を最小化し、ABC352 Fの解説では相対順位を求めた後に成分の配置を考える。
ABC280 Fの解説では、辺は移動による得点の増減を表す。加法の閉路和が非零なら、全辺を満たす頂点値の等式系は不整合である。一方、原問題では辺を何度でも往復でき、非零の閉路を正の利得になる向きで繰り返せる。その成分内の始点・終点への移動を前後に付ければ、得点をいくらでも増やせるため答えが inf になる。これは移動の得点を最大化する問題固有の結論であり、等式制約に解があるという意味ではない。
問題一覧
- ABC396 E「Min of Restricted Sum」 公式問題組合せ: 成立証明から構成解を復元する
技能・出典
主題: 静的graph等式制約のpotential伝播(辺等式をDFS/BFSでroot-relative potentialへ伝播し、cycle矛盾を検出して各連結成分の全解を自由offset一つで表現・復元できる。)。既習技能: 成立証明から構成解を復元する(成立証明に対応する親・局所操作・選択を記録し、要件を満たす構成を出力できる。)。主タグ: 静的graph等式制約のpotential伝播 / 補助タグ: 構成解・witness復元
- ABC280 F「Pay or Receive」 公式問題
技能・出典
主題: 静的graph等式制約のpotential伝播(辺等式をDFS/BFSでroot-relative potentialへ伝播し、cycle矛盾を検出して各連結成分の全解を自由offset一つで表現・復元できる。)。
各問題の解説は問題ごとの本文として執筆します。各項目には主題・追加で学ぶ技能・既習技能の役割を示します。
関連問題
他の主題と組み合わせる問題を読む
以下はこのUnitのOutcomeを追加で学ぶ技能または既習技能として参照する、別のUnitを主題とする問題です。
- ABC352 F「Estimate Order」 公式問題主題: 部分集合・bitmask状態DP
技能・出典
主題: 部分集合・bitmask状態DP(bitmaskの各bitが表す意味を定め、部分集合間の遷移を正しく設計できる。)。既習技能: 静的graph等式制約のpotential伝播(辺等式をDFS/BFSでroot-relative potentialへ伝播し、cycle矛盾を検出して各連結成分の全解を自由offset一つで表現・復元できる。)。主タグ: 部分集合・bitmask状態DP / 補助タグ: 静的graph等式制約のpotential伝播
前提・学習成果・出典
習得対象の目安: 水色(1200–1599)。辺の差やXORを伝播し、閉路の整合性と成分ごとの自由度を確認する。
対象色の読み方は本書の読み方を参照してください。
概念上の親: 連結成分を管理し縮約する。問題へ進む前に、下記の直接前提のうち未習得の単元を確認する。
Canonical taxonomy: FinalTaxonomyBuild final-taxonomy-build-initial digest f1ae39bc7201c3374c108e800284e1e0068ce6f7a57f15b2a9e5219616e3c4fe / LearningUnit unit-graph-potential-propagation
静的graph等式制約のpotential伝播
習得する技能
- 辺等式をDFS/BFSでroot-relative potentialへ伝播し、cycle矛盾を検出して各連結成分の全解を自由offset一つで表現・復元できる。
前提と範囲
共通前提: prereq-abc-advanced-v1 (1.0.0)。
直接の前提単元: 状態グラフのモデリングと探索。
このUnitを直接前提とする単元: potential・weighted DSU。
通常のDFS・BFSを土台に、辺等式からroot-relative potentialを静的に伝播し、cycle整合性と成分offsetの自由度を分離する。
このUnitでは扱わないもの
- 静的graph等式制約のpotential伝播の発動条件・不変量を使わず、実装部品だけを偶然共有する解法。