Editorial - Next DP Contest

S - 2 枚の扉 / Two doors Editorial by iastm

図解

この記事の目的は、図解を通して平面グラフの性質を直感的に理解してもらうことです。平面グラフの概念を知らない読者を想定しているため、証明以外の部分では、できるだけ伝わりやすさを重視します。

まず、$N=3$ の例を観察して、どのようなグリッドに対しマス $(1, 1)$ と $(3, 3)$ が連結であるか考えてみましょう。

例 1, 2, 3 の代替テキスト

例1：パス(1,1),(1,2),(2,2),(3,2),(3,3)の途中で通行不可な辺がないので、(1,1)と(3,3)は連結である。

例2：(3,1)と(3,2)の間、(2,2)と(3,2)の間、(2,2)と(2,3)の間、(1,2)と(1,3)の間、計4箇所の通行不可な壁が設置されており、下のボーダーから上のボーダーまでが壁で繋がっている。(1,1)と(3,3)は連結でない。

例3：(2,1)と(2,2)の間、(2,2)と(3,2)の間、計2箇所の通行不可な壁が設置されている。そのほか、(1,3)と(2,3)の間に扉A、(3,2)と(3,3)の間に扉B、(1,2)と(2,2)の間に普通の扉がすべて封鎖済みであり、下のボーダーと右のボーダーが通行不可な場所で繋がっている。(1,1)と(3,3)は連結でない。

例 1 ではマス $(1, 1)$ と $(3, 3)$ が連結です。例 2 と例 3 では、壁がグリッドの外部の左下から右上まで途切れずに繋ぎ、マス $(1, 1)$ と $(3, 3)$ の属する連結成分を切断しています。この記事ではグリッドの外部を「ボーダー」と呼びます。一般には、マス $(1, 1)$ と $(N, N)$ が連結であることと、「壁や封鎖済みの扉だけを辿って、左下のボーダーから右上のボーダーに到達することができないこと」は同値です。（言い換え後の条件では、マス自体が移動先でないことに注意してください。）

平面グラフの言葉で言い換えると？

各隣接するマス同士に対し、通行可能なら容量 $1$、通過不可なら容量 $0$ の無向辺で結びます。最大フロー最小カット定理より、元のグリッドにおいてマス $(1, 1)$ から $(N, N)$ に向かうパスが存在することは、最小 $(1, 1)$-$(N, N)$ カットが $0$ ではないことと同値です。

ここでマス $(N, N)$ から $(1, 1)$ に向かう、容量が無限大の有向辺 $e^\ast$ を追加します。$e^\ast$ を追加しても最小 $(1, 1)$-$(N, N)$ カットは変わりません。また、$e^\ast$ を追加することで、グリッドの外部を $2$ つの面に分けることができます。この $2$ つの面は先述の「左下のボーダー」と「右上のボーダー」に対応します。

$e^\ast$ を追加して得られるグラフは平面グラフです。平面グラフの頂点が面に、面が頂点に対応する双対グラフ（具体例は後述）を考えると、左下のボーダーと右上のボーダーを結ぶパスが横切る辺の集合は、平面グラフにおけるカットセットに一致します。したがって、辺の容量をそのまま双対辺の重みとみなすと、左下のボーダーと右上のボーダーの最小パスの長さは、平面グラフでの最小カットに等しいです。

例えば例 2 では、$4$ つの壁がパスとして $2$ つのボーダーを結んでおり、カット $(\lbrace(1, 1), (1, 2), \dots\rbrace, \lbrace(1, 3), (2, 3), \dots, \rbrace)$ のカットセットにも対応します。この場合、最小パスの長さと最小カットは共に $0$ です。

よって、次は全て同値です。

元のグリッドにおいて、マス $(1, 1)$ と $(N, N)$ が連結
平面グラフにおいて、最小 $(1, 1)$-$(N, N)$ カットが $0$ ではない
双対グラフにおいて、左下のボーダーと右上のボーダーの最小パスの長さが $0$ ではない
双対グラフにおいて、容量 $0$ の辺（つまり壁や封鎖済みの扉）のみ辿って、左下のボーダーから右上のボーダーに到達できない

ここまで読んで「元の問題の解き方がわかっちゃったカモ！？」と思ったら、ぜひ頑張って挑戦してみてください。

グリッドの双対グラフを用いて、この条件を言い換えることを考えます。具体的には、

左下のボーダーを表す頂点 $X$
右上のボーダーを表す頂点 $Y$
マスの四隅を表す $(N-1)^2$ 個の頂点 $1, 2, \dots, (N-1)^2$
各壁を表す辺
各扉を表す辺

からなるグラフを作ります。下図は先程の例に対応する双対グラフです。これを元に、条件を満たす扉の封鎖方法が存在するか考えてみましょう。

例 4, 5, 6 の代替テキスト

例4：例1の双対グラフを表す。このグラフでは、頂点XとYは連結でない。

例5：例2の双対グラフを表す。このグラフでは、壁の辺だけでパス(X,3,4,2,Y)を辿ることができるため、頂点XとYは連結である。ここで頂点1,2,3,4は中央の四隅を上から下、左から右に番号を振ったものである。

例6：例3の双対グラフを表す。封鎖済みの扉と壁でパス(X,4,3,1,2,Y)を辿ることができるため、頂点XとYは連結である。ここで扉Aと扉B以外の封鎖された扉は1枚のみ。

例 4 では、どのように扉を封鎖しても、$X$ と $Y$ が連結になることはありません。したがって元のグリッド（例 1）は常に良い状態であり、条件を満たす封鎖方法は存在しません。

例 5 では、どのように扉を封鎖しても、$X$ と $Y$ は連結です。元のグリッド（例 2）は常に良い状態でないため、条件を満たす封鎖方法は存在しません。

例 6 では、頂点 $1$ と $2$ の間の扉を封鎖すると、

$X$ と $Y$ は連結でないため、元のグリッド（例 3）は良い状態である。
扉 $A$ と扉 $B$ のちょうど一方を封鎖した場合、$X$ と $Y$ は連結でないため、元のグリッドは良い状態である。
扉 $A$ と扉 $B$ の両方を封鎖したとき、$X$ と $Y$ は連結であるため、元のグリッドは良い状態でない。

したがって、条件を満たす扉の封鎖方法が存在します。また、封鎖する扉の最小枚数は $1$ です。

元の問題の条件を満たす封鎖する扉の選び方を「良い選び方」と呼びます。以上の観察を整理すると、良い選び方の必要十分条件は以下の通りです。

扉 $A$ と扉 $B$、および封鎖すると決めた扉だけを残し、それ以外の扉を双対グラフから消して得られるグラフについて、以下が成り立つ。
1. $X$ と $Y$ は連結である
2. 全ての $X$-$Y$ パスは扉 $A$ と扉 $B$ の両方を通る

平面グラフの言葉で言い換えると？

扉 $A$ と扉 $B$ を含め、封鎖する扉の集合を固定します。壁と封鎖済みの扉は重み $0$、その他の扉は重み $1$ の辺に対応します。

必要性を示します。まず、「扉 $A$ と扉 $B$ の両方を封鎖したとき良い状態でない」という条件は、「扉 $A$ と扉 $B$ の両方が重み $0$ の辺に対応するなら、最小 $X$-$Y$ パスの重みが $0$ である」と同値です。そのため、双対グラフから重み $1$ の辺を消すことを考えると、条件 1 が得られます。

次に、「扉 $A$ と扉 $B$ を同時に封鎖していないとき良い状態である」という条件の対偶は、「重み $0$ の $X$-$Y$ パスが存在するなら、扉 $A$ と扉 $B$ の両方が重み $0$ の辺に対応する」となります。もしも扉 $A$ の重みが $1$ であるにもかかわらず、扉 $A$ を通らずに重み $0$ を達成する $X$-$Y$ パスが存在するなら、対偶に矛盾します。このことから、重み $0$ の $X$-$Y$ パスは扉 $A$ を通らなければなりません。扉 $B$ についても同様です。したがって、双対グラフから重み $1$ の辺を消したとき、全ての $X$-$Y$ パスは扉 $A$ と $B$ の両方を通ります。これより条件 2 が得られます。

最後に、十分性を示します。$X$ と $Y$ が連結であって、全ての重み $0$ のパスが扉 $A$ と $B$ の両方を通る場合を考えます。双対グラフにおける各パスはグリッドにおけるカットセットに一致するため、重み $0$ のカットセットは常に扉 $A$ と $B$ の両方を含みます。よって双方の扉を封鎖したとき、そのときに限り重み $0$ のカットが存在し、グリッドが良い状態でなくなります。これを満たす扉の選び方は良い選び方です。

壁を通じて同じ連結成分にある頂点は扉の選び方によらないので、最初から $1$ つの頂点として扱って構いません。そのため、壁を縮約して得られるグラフについて良い選び方の条件は変わりません。また、縮約後の双対グラフに残る辺は全て扉なので、$X$ から $Y$ に向かうパスの長さは封鎖された扉の枚数に対応します。自己辺や多重辺を適切に取り除いてから以下の答えを求めれば、元の問題を解くことができます。

$X$ から $Y$ に向かうパスであって、扉 $A$ と $B$ の両方を通るものが存在するか判定し、存在するならその長さの最小値を求めよ。

帰着後の問題を整理します。

$n$ 頂点 $m$ 辺の単純無向グラフにおいて、頂点 $s$ から $t$ に向かう、指定された $2$ 本の辺を全て通るパスが存在するか判定し、存在するならその長さの最小値を求めよ。

DP を使って最小パスの長さを求めることを考えます。$f(d, v, E)$ を「$s$ から $v$ に向かう長さ $d$ のパスであって、指定されたかつ未探索の辺集合が $E$ であるものが存在するか」を示す真理値として定義します。遷移として、$f(d, v, E)$ の値は各辺 $\lbrace u, v\rbrace$ について適当な $f(d-1, u, E^\prime)$ の値から求められます。$n$ 頂点以下のパスの辺数は高々 $n-1$ なので、$f(d, t, \text{\O})$ が真である非負整数 $d\leq n-1$ が存在するかを判定し、存在するなら最小の $d$ を求めることで最小パスの長さが得られます。

この DP を確認してみましょう。下図の例 7 について、頂点 $10$ から頂点 $7$ に向かうパスであって、辺 $\lbrace1, 6\rbrace, \lbrace5, 9\rbrace$ の両方を通るパスの長さの最小値を求めてみてください。

例 7, 8, 9 の代替テキスト

例7：10頂点からなるグラフがあり、起点10、終点7、および通る必要のある辺(1,6)と(5,9)が示される。

例8：例7の不正解として、ウォーク(10,9,5,1,6,9,7)が示される。

例9：例7の正解として、パス(10,9,5,1,6,3,4,7)が示される。

例 8 の探索順は $(10, 9, 5, 1, 6, 9, 7)$ です。指定された辺を全て通っていますが、頂点 $9, 5, 1, 6$ からなる閉路が含まれるため、これは条件を満たさないウォークです。

例 9 の探索順は $(10, 9, 5, 1, 6, 3, 4, 7)$ です。指定された辺を全て通っており、かつ各頂点を $1$ 回以下通っているため、これは条件を満たすパスです。また、この例の長さの最小値は $7$ です。

DP が正しく動作するには、例 8 のような閉路を正しく検出する必要があります。しかし、現在の $f$ に含まれる「～を満たすパスが存在するか」という情報だけでは検出が難しいでしょう。

解決策として、標数 $2$ の体 $\mathbb{F}_{2^k}$ を用いたハッシュ関数を紹介します。今回は特に、任意の元 $x\in\mathbb{F}_{2^k}$ について $x+x=0$ が成り立つ性質を利用します。$\mathbb{F}_{2^k}$ の演算や実装については、以下の nim product に関する資料も参考になります。

kyopro_friend’s diary. Nim product.

各辺 $e$ に独立かつ一様ランダムに重み $c_e\in\mathbb{F}_{2^k}$ を割り当て、各ウォーク $w$ の重みを辺の重みの積 $\prod_{e\in w}c_e$ として定義します。また、$g(d, v, E)$ を「～を満たすウォークの重みの和」として定義します。

例 8 の閉路について、今度は $g$ を用いた DP の動作を観察します。$g(5, 9, \text{\O})$ を計算する時点で、閉路を含むウォーク $(10, 9, 5, 1, 6, 9)$ の重みが加算されますが、逆方向からもウォーク $(10, 9, 6, 1, 5, 9)$ の重みが加算されます。これらは辺集合として一致するため、重みの和が $0$ となります。

一般に、単純でないウォークに含まれる閉路部分を逆向きに辿ったウォークを考えると、両者は同じ辺を同じ回数だけ使うため重みが等しく、寄与が打ち消し合います。一方、相異なるパス同士が同じ辺集合を持つことはないため、単純でないウォークのように寄与が打ち消し合うことはありません。したがって、$g$ に残ったパスの寄与が非零であるか調べることで、$f$ の真偽を判定することができます。ただし、相異なるパスの重みの和は偶然 $0$ になる場合があります。この確率については後で評価します。

ところが、同じ辺を往復するウォークは、逆向きに辿っても同じウォークになってしまうため、別のウォークと寄与が打ち消し合うことがありません。下図の例 10 では $g(3, 9, \text{\O})$ を計算する時点で、閉路を含むウォーク $(10, 9, 5, 9)$ の重みがそのまま加算されます。そこで、DP の状態に「直前の移動で使われた辺」を追加し、遷移に「同じ辺を連続して通ってはならない」という制約を加えることで、同じ辺を往復するウォークの寄与を除去することができます。

なお、直前の移動で使われた辺とウォークの向きが分かれば、現在の頂点は一意に定まります。そのため、$g$ に加え、

ウォークの長さ $d$
直前の移動で使われた辺とその向き $e^\prime$
指定されたかつ未探索の辺集合 $E$

を満たすウォークの重みの和として定義される $h(d, e^\prime, E)$ を管理すればよいです。

例 10 の代替テキスト

例10：例7のグラフから辺(1,5)が消され、通る必要のある辺が(5,9)と(9,10)になっている。この例では頂点5と隣接する頂点は頂点9のみである。

以上が DP 解法の概要です。次に、最小パスの長さを誤って出力する確率を評価します。

まず、条件を満たす長さ $d$ のパスが存在しないのに「存在する」と判定すること（偽陽性）はありません。実際、打ち消し合いの結果、$g$ に寄与するのは条件を満たすパスだけです。そのため、$g(d, t, \text{\O})$ が非零ならば、条件を満たす長さ $d$ のパスは必ず存在します。

一方、パスが存在する場合でも、複数のパスの寄与が偶然打ち消し合って $0$ となる可能性があります。真の最小パスの長さを $d^\ast$ とし、条件を満たす長さ $d^\ast$ のパスが存在するにもかかわらず「パスが存在しない、もしくは最小パスの長さが $d^\ast$ より大きい」と判定すること（偽陰性）の確率を評価します。

$\mathcal{P}^\ast$ を、$s$ から $t$ に向かう、指定された辺を全て通る長さ $d^\ast$ のパスの全体集合とします。すると、判定結果が偽陰性となることは

\[g(d^\ast, t, \text{\O})=\sum_{P\in{\mathcal{P}^\ast}}\prod_{e\in P}c_e=0\]

と同値です。各パスに対応する単項式は互いに異なるため、$g(d^\ast, t, \text{\O})$ は $m$ 個の不定元 $c_e$ に関する非零多項式です。また、パスの長さは $d^\ast$ であるため、この多項式の全次数は $d^\ast$ です。DeMillo–Lipton–Schwartz–Zippel の補題より、各 $c_e$ を $\mathbb{F}_{2^k}$ から独立かつ一様ランダムに選んだとき、$g(d^\ast, t, \text{\O})=0$ となる確率は

\[\frac{d^\ast}{2^k}\]

以下です。$d^\ast\leq n-1$ であり、かつ判定結果が偽陽性とならないことから、この解法が最小パスの長さを誤って出力する確率は

\[\frac{n-1}{2^k}\]

以下です。

$\mathbb{F}_{2^k}$ 上の加算・乗算を定数時間で行えるとみなすと、各 $d, E$ における $g, h$ の計算は $n$ 個の頂点と $m$ 本の辺の遷移を求めればよいため $O(n+m)$ 時間です。加えて $d\in\lbrace0, 1, \dots, n-1\rbrace$ は $n$ 通り、$E$ は $2^2$ 通りまで考えればよいので、全体の計算量は $O(n(n+m))$ です。

元の問題では $n\leq (N-1)^2+2$ かつ $m\leq 2N(N-1)$ なので、$O(N^4)$ 時間で解けます。また、$N\leq40$ かつ $k=64$ とする場合、

\[\frac{n-1}{2^k}\lt9\times10^{-17}\]

より、答えを誤って出力する確率は $9\times10^{-17}$ 未満となります。

参考文献

Dorit S. Hochbaum. Lecture Notes for IEOR 266: Graph Algorithms and Network Flows.
岩田陽一. 指数時間アルゴリズムの最先端.