考察
区間和を累積和の差で表すと、各条件を二つの変数の関係へ変換できる。正整数列 に対して 、 と置く。区間和の条件は 、正値条件は となる。
等式を二本の不等式へ分ければ、すべて 型の差分制約になる。この制約を、頂点 から へ向かう重み の辺で表す。
- 各区間和には、 の重み と、 の重み の二辺を張る。
- 各 には、 の重み の辺を張る。
全 を定数だけずらしても差は変わらない。そこで、ここからは となるよう平行移動した変数を同じ と書く。元の総和は なので、総和の最小化は の最大化に変わる。 から への経路に沿って不等式を足すと、 はその経路の重みの総和以下になる。最も厳しい上界が最短距離であり、負閉路がなければ、その距離を各変数に割り当てて上界を達成できる。
採用する候補: へ平行移動し、差分制約グラフの最短路で最大可能な を求めて答え を得る
各制約を有向辺にし Bellman–Ford 法を使えば、負閉路による実行不能判定と目的値の最適化を で同時に扱える。
棄却する候補: 区間和の等式だけを連立方程式として解き、未決定変数を任意に埋める
の不等式と総和の最小化を反映できず、整合する等式系でも正整数解が存在しない場合を判定できない。
頂点は の 個である。負閉路がなければ、最短路は頂点を重複しない経路として選べるので、使う辺は高々 本になる。この 距離を求める 段 と、負閉路を調べる追加の一段 を区別する。
ここでは、一段前の配列だけを参照する同期緩和で説明する。 を「始点 から頂点 へ、高々 本の辺を使う歩道の重みの最小値」とする。歩道とは頂点や辺の重複を許す経路のことで、該当する歩道がなければ値は とする。
-
、それ以外を にする。
-
の順に、次の式で全頂点の値を求める。まず次の配列へ前段の値をコピーし、すべての辺について前段の配列から候補を計算する。
内側の最小値は、 へ入る重み の辺すべてについて取る。到達していない からの候補は使わない。
-
同じ方法でもう一段だけ進め、 となる頂点が一つでもあるか調べる。あれば負閉路があるので -1、なければ を出力する。
例えば では、初期状態は である。重み の辺 により、第 段で に改善する。しかし第2段では改善せず、答えは である。実際に が条件を満たす。第 段での更新だけを見て不可能と判定してはいけない。
また、辺 があるため、始点 から全頂点へ到達できる。従って、始点から到達可能な負閉路を検出すれば、グラフ全体の負閉路、つまり全制約の矛盾を調べられる。
典型の発動条件
累積和による区間制約変換
発動条件: 多数の区間和の等式・不等式を同時に扱うとき。
区間和を二つの prefix sum の差として、変数二個の制約へ変える。
差分制約と Bellman-Ford
発動条件: 制約が に統一でき、実行可能性と一変数の極値が必要なとき。
制約を有向辺へ写し、最短距離と負閉路検出で最大 を求める。
問題固有の要素
総和を直接最小化せず終点を 0 に固定して始点を最大化すると、区間和の平行移動不変性が最短路の目的関数へ一致する。
別の問題へ持ち帰る視点: 差だけで定まる変数系では一変数を固定して平行移動自由度を消し、求める差を別頂点の極値として読む。
正当性
各区間等式は逆符号の二辺、正値条件は重み の辺 に一致する。負閉路上の不等式を足すと、 が負数以下という矛盾を得るので、負閉路があれば条件を満たす列は存在しない。
同期緩和では、前段の歩道をそのまま使う場合と、最後の一辺を足す場合を合わせるため、 は高々 辺の歩道の最小重みになる。負閉路がなければ、歩道中の閉じた部分は重みが非負なので取り除ける。従って最短距離は高々 辺で達成でき、 で確定して第 段では改善しない。
逆に、第 段で改善しなければ、全辺について が成り立つ。全頂点へ到達できるため、これらはすべて有限値の不等式であり、負閉路があるという仮定とは矛盾する。よって追加の一段で改善することと、負閉路が存在することは同値である。
負閉路がなければ であり、 は全差分制約を満たす。辺重みが整数なので も整数で、正値条件と区間和の条件を満たす。一方、 を満たす任意の実行可能解は、経路上の不等式の和より である。従って距離の割り当ては最大の を達成し、その負値 が最小総和となる。
実装上の注意
- 距離と加算には64 bit整数を使う。到達不能を表す値には辺重みを加えない。等式の両向き辺と正値条件の向きを取り違えない。
- 同期版は前段と次段の二配列を使う。途中で書き換えた次段の値を参照すると、「高々 辺」という段の意味が変わる。
- 一配列をその場で更新する実装では、全辺を一通り調べる操作を1回の走査とし、 回走査した後、追加の第 回で改善があるか調べる。この実装も負閉路がなければ 回までに最短距離が確定するが、同じ走査中に複数の辺を伝わるので、1回の走査を厳密に1辺分の進行とは解釈しない。更新がない走査では以後も変わらないため、途中で打ち切ってよい。
復習の核
- 同一区間に異なる がある矛盾、 が区間長未満、制約のない位置を含む例、 を小さい の全探索と照合する。
- 負閉路判定では頂点数を数える。 頂点なら有限最短距離を求めるのは 段、矛盾を検出するのは追加の第 段である。
計算量と制約
時間
頂点数は 、辺数は 。グラフ構築に 、同期緩和は追加判定を含む 段で、各段に配列のコピーと全辺の走査で かかる。全体は 時間となる。
空間
辺リストに 、前段と次段の二配列に を使い、全体で 空間となる。全段の配列を保存する必要はない。
制約との対応
公式制約は 、、。辺数は最大12,000本、追加判定を含めても全辺の走査は約4,800万回である。制限時間は2秒、メモリ制限は1024 MiB。
出典