G - Tatami Editorial by Nyaan
別解として、最大二部マッチングに帰着させる解法があるので紹介します。
説明を簡単にするため、以下の解説では上から \(i\) 行目, 左から \(j\) 列目のマスに番号 \(i \times W + j\) を対応させてマス目を整数 1 個で表します。
まず、解法は次の通りです。
解法
\(\lbrace 1, 2, \dots, HW \rbrace\) および \(\lbrace 1', 2', \dots, HW'\rbrace\) を部集合とする \(2HW\) 頂点の二部グラフ \(G\) を考える。
ここで、すべての隣接するマスの組 \((i, j)\) について、マス \(i\) が2
であり、かつ マス \(j\) が1
でないときに \(G\) の頂点 \(i\) と 頂点 \(j'\) の間に辺が張られている。
このとき \(G\) の最大マッチングの辺の本数がグリッドに含まれる2
の個数と一致していれば答えはYes
, そうでない場合は答えはNo
である。最大マッチングは Dinic 法で \(\mathrm{O}((HW)^{1.5})\) で十分高速に計算できる。
解法の正当性を説明します。
あるマッチングに対して、次の条件を満たす \(x\) を invalid なマス と呼びます。
- 相異なる整数 \(y,z\) があって、頂点 \(x\) は マッチングで \(y'\) と、頂点 \(x'\) は \(z\) と結ばれている。
また、次の条件を満たすマッチングを valid なマッチング と呼びます。
- 辺の数がグリッドに含まれる
2
の個数と一致している。 - invalid な マスが存在しない。
\(G\) が valid なマッチングを含むとき、畳の敷き方は、すべてのマッチングに含まれる辺について 辺の両端を覆う位置に 1x2 の畳を敷き、それ以外のマスに 1x1 の畳を敷けば valid な畳の敷き方になります。逆にすべての valid な畳の敷き方を \(G\) における valid なマッチングに対応させることもできるので(詳細略) 、畳の敷き方の存在判定は \(G\) における valid なマッチングの存在判定と同値です。
最大流が 2
の個数と一致しないときは 明らかに valid なマッチングは存在しません。 一致する場合に必ず valid なマッチングが存在することを証明します。
辺の本数が 2
の個数と一致するマッチング を任意に 1 つ取り \(m\) とします。\(m\) に対して次の一連の操作を \(0\) 回以上作用させます。
- \(m\) が invalid なマスを含まない場合、操作を終了する。invalid なマスがあるとき、1 つ取り \(x\) とする。
- 空の列 \(a\) を用意する。次の操作を繰り返す。
- \(a\) に \(x\) を追加する。
- \(a\) に \(x\) が \(2\) 個以上含まれている場合、繰り返しを終了する。
- マス \(y\) を、頂点 \(x'\) と頂点 \(y\) がマッチングされているようなマスとする。
- \(y\) が invalid なマスでない場合は、頂点 \(y'\) はマッチングに使用されていない頂点である。よって頂点 \(x\) のマッチング先を \(y'\) に変更して、操作全体を終了する。
- 注釈:\(x'-y\) 間に辺があるので \(y\) は
2
が書かれたマスであるから \(x-y'\) 間に辺が存在する。
- 注釈:\(x'-y\) 間に辺があるので \(y\) は
- \(y\) が invalid なマスである場合 \(x \gets y\) と \(x\) の値を更新して、繰り返しの最初に戻る。
- 繰り返しを break した時点でのマスの列を \(a = (a_0, a_1, \dots, a_{|a|})\) とする。端点が \(a\) に含まれるマッチングの辺を\((a_0,a_1'), (a_0', a_1 ), (a_2,a_3'), (a_2', a_3), \dots\) に張り替えて操作を終了する。
- 注釈:マス \(x\) に対して頂点 \(x, x'\) はマッチングに高々 1 回しか登場しないことに注目すると \(a_0 = a_{|a|}\) が確認できて、ここからマスの列 \(a\) はグリッドグラフ上のサイクルになるとわかる。グリッドグラフの二部性からサイクルは偶数長であり 2 個ずつに分けることができる。また、\(a\) に含まれる頂点はすべて
2
が書かれたマスなので 隣接するマス \((x, y)\) すべて \(x-y', x'-y\) 間に辺が存在する。
- 注釈:マス \(x\) に対して頂点 \(x, x'\) はマッチングに高々 1 回しか登場しないことに注目すると \(a_0 = a_{|a|}\) が確認できて、ここからマスの列 \(a\) はグリッドグラフ上のサイクルになるとわかる。グリッドグラフの二部性からサイクルは偶数長であり 2 個ずつに分けることができる。また、\(a\) に含まれる頂点はすべて
1 回の操作によって、 \(m\) の辺数は変わらないまま \(m\) に含まれる invalid なマスを 1 個以上減らすことができます。よって、\(m\) に invalid なマスが含まれない状態になるまで 高々 \(HW\) 回操作を行えば \(m\) を valid なマッチングにすることができます。
よって、マッチングの辺の本数が 2
の個数と一致していれば必ず valid なマッチングが存在することが証明できました。以上より解法の正当性も証明しました。
posted:
last update: