本問題の解法

この問題は、グリッドグラフの部分グラフと、そのグラフ上の \(2\) 点が与えられ、交互に頂点を取り除いていって、先に \(2\) 点 を非連結にした方が勝ちというゲームの勝者を求める問題に等しいです。

’S’と書かれた頂点を\(s\)、’G’と書かれた頂点を\(t\), \(s\) と \(t\) を非連結にするために取り除く頂点の最小数を \(k\) とします。問題の制約より \(1\leq k \leq 4\)になります。

初期の状態で、 \(k = 1\) の場合 Alice が勝利します。 \(k\geq 2\) の場合、各操作によって、\(k\)の値は、変わらないか、\(1\) 減るかです。 自分の操作後に \(k\) を\(2\) から \(1\) に変化させたプレイヤーは敗北しますが、\(k = 0\) になるまで、ゲームは終わらないので、いずれかのプレイヤーは、\(k\) を \(2\) から \(1\) にしなければいけません。 初期状態で \(k \geq 2\) の場合、そのような操作をすることがゲームに敗北する必要十分条件です。 \(k = 2\) の場合に、どの点を取り除いても、\(k = 1\) に変化してしまう状況を考えます。このとき次が成立します。

命題: \(k=2\) かつ、どのような頂点を取り除いても、\(k\) が \(1\) に変化してしまう場合、残っている頂点の個数は必ず偶数である。

証明: \(k=2\) の場合、Menger の定理より、\(s\) から \(t\) に \(2\) 組の点素パスが存在します。(Mengerの定理の主張などは後述します.。) この点素パスに含まれない点が存在するなら、そのような点を取り除くことで、 \(k = 1\) に変化しない手を打てます。 つまり、どの点を取り除いても、\(k\) が \(2\) から \(1\) に変化するなら、どのような \(2\) 組の点素パスを取ってきても、その\(2\) 組のパスに含まれない点がグラフ上に存在しないことが必要条件となります。 与えられるグラフは二部グラフなので、\(2\) 組の点素パスに含まれる頂点の集合、つまり残っている頂点数は偶数になります。

頂点を消す操作は交互に行うので、ゲームの勝敗は初期状態で残っている頂点の偶奇で決定します。

以上をまとめると、 \(k = 1\) の場合、Aliceが勝利します。 \(k \geq 2\) の場合、” . “ と書かれた頂点の個数が偶数ならBobが、奇数ならAliceが勝利します。

\(k\) の値はフローのアルゴリズムなどを用いて、テストケース当たり O(\(HW\)) で計算できます。

Menger の定理について

Menger の定理とは以下の定理を指します。

・無向(有向)グラフにおいて、ある \(2\) 組の頂点 \(s,t\) について、 \(s\) から \(t\) に到達不可能にするために取り除く辺の最小数は、\(s\) から \(t\) の辺素パスの最大数に等しい。

・無向(有向)グラフにおいて、隣接していない \(2\) 組の頂点 \(s,t\) について、\(s\) から \(t\)に到達不可能にするために取り除く頂点の最小数は、\(s\) から \(t\) の点素パスの最大数に等しい。

有向グラフで辺を取り除いて \(2\) 点を非連結にする場合、取り除くべき辺数の最小値は最小カットであり、最大流最小カット定理より、辺素パスの本数の最大値に等しいことが知られていますが、Menger の定理も同様のことを述べています。 本解説中での \(k\) の値は、頂点を取り除いて、ある \(2\) 点を非連結にする場合に取り除くべき頂点数の最小値であり、この値は点素パスの本数と対応するというのが Menger の定理の主張です。 Menger の定理は、最大流最小カット定理から示すことができます。取り除くべき頂点の最小値がフローのアルゴリズムを用いて計算できるのは、このような数理的な背景があります。

辺削除ではなく、点削除に関するフローの問題を解く場合には、適切に頂点を倍加したりしますが、その手法は、 Menger の定理の証明において、有向かつ辺削除に関する主張を、有向かつ点削除に関する主張に応用する際に、そのまま用いることができます。実際、上記の命題の証明中で、「Menger の定理より」と記載した箇所は、頂点を倍加したグラフにおける最大流最小カット定理を用いても導出できます。

より詳細な証明は37zigenさんのHPなどを参照してください。 https://37zigen.com/menger-theorem/

書籍ですが、組合せ最適化 (著: B. Korte, J. Vygen) という本などにも証明が記載してあります。