考察
同時に置けない二マスの関係をグラフの辺で表すと、置けるコマの最大化は「辺の両端を同時に選ばない頂点集合」の最大化になる。鍵は、この競合グラフを常に二色で塗り分けられることである。二部グラフなら、最大matchingから最小頂点被覆を復元し、その補集合として最大配置を取り出せる。
空きマス数を とする。各マスに置く・置かないを全探索すると 通りあり、最大 の盤面には使えない。そこで、空きマスを一つずつ頂点にし、変位 または で結ばれる二つの空きマスの間に無向辺を置く。求めるのは、このグラフの最大独立集合である。独立集合とは、内部に辺を持たない頂点集合をいう。
一般のグラフで最大独立集合を求めるのは難しいが、今回は辺が一定の座標変位に限られる。まず、移動するたびに色が反転する塗り方を探そう。
gcdで移動量の共通因子を取り除く
以後、行・列の座標 はともに0始まりとし、 とする。通常の市松模様、すなわち では、 が偶数のときに色が変わらない。例えば では、 と は攻撃し合うのに同色になる。
移動量に共通の因子があるなら、それを取り除いた尺度で偶奇を調べたい。そこで
と置く。 より なので、 でも割れる。色を決めるための座標を
とする。整数 に対して
だから、攻撃による の差は正負も含めて または になる。端数の位置に依存せず、割った移動量そのものが座標の差になる点が重要である。
なので、偶奇は次の二場合だけである。
- 両方が奇数なら、色を とする。行方向の差は または で必ず奇数なので、色が反転する。
- 一方だけが奇数なら、色を とする。行列和の差は で必ず奇数なので、色が反転する。
なら なので、行を2行ずつ区切って色を交互にすればよい。先ほどの と は、それぞれ色0と色1になる。 なら で後者を使う。 から攻撃できる と はともに色1となり、行方向の変位が0でも問題ない。
この座標の写し方は彩色のためだけに使う。同じ や同じ色になったマスも、一つの頂点へ併合しない。例えば と が同じ色でも、置く・置かないは別々に選べる。盤内の空きマスはすべて元の頂点として残し、壁と盤外の移動先だけを除く。全盤面で攻撃辺の異色性を示したので、壁の位置によらず二部グラフになる。
最大個数から配置の復元へ
色0の空きマス集合を 、色1を とする。端点を共有しない辺の集合であるmatchingを最大化し、その辺数を とする。Kőnigの定理より、すべての辺の少なくとも一端を含む最小頂点被覆の大きさも である。被覆の補集合を選べば攻撃辺の両端を同時に選ばず、最大個数 の配置になる。
ただし、この問題では個数だけでなく配置そのものを出力する。matchingの各辺から片方の端点を任意に除くだけでは、matchingに入らなかった攻撃辺が残り得る。最小頂点被覆を、次の交互路探索で具体的に取り出す。
- 各空きマスに頂点IDと元の座標を対応させ、上の式で色を決める。各 頂点から八方向の移動先を調べ、盤内かつ空きマスの場合だけ への辺を加える。
- 最大matchingを求め、各頂点の相手を
mate に保存する。相手がいない頂点は未使用とする。Hopcroft–Karp法を使うか、始点 から 、攻撃辺を 、 から終点 へすべて容量1の辺を置き、Dinic法で最大流を求める。後者では流量1の攻撃辺がmatchingとなる。
- matchingで未使用の の全頂点をキューへ入れ、到達済みにする。 からはmatchingに含まれない辺を へ進み、 からはmatchingに含まれる辺を相手の へ進む。未訪問の頂点だけを追加し、キューが空になるまで探索する。
- 到達した左・右の集合をそれぞれ とする。最小頂点被覆は なので、コマを置く集合としてその補集合 を選ぶ。
- 入力の盤面をコピーし、選んだ頂点の元のマスだけを
o に変えて 行を出力する。選ばなかった空きマスは .、壁は # のままにする。 は選んだ個数の確認に使い、個数自体を別に出力する必要はない。
交互路から最小頂点被覆が得られる理由は主単元のKőnigの定理と被覆復元を参照する。本問では、そこで選ぶ頂点を元のマスへ戻すところまでが必要である。
典型の発動条件
二部 graph の最大独立集合
同時に選べない二要素の関係を辺にでき、競合グラフの二部性を証明できるときに使う。配置と独立集合の対応を両方向に確認し、最大matchingから最小頂点被覆、その補集合へ進む。実際の選択集合が必要なら、最大個数の式だけで終えず、交互路から被覆も復元する。
gcd・parity による特殊彩色
格子上の辺が固定の変位で結ばれるときは、変位の共通因子を取り除き、どの座標の偶奇が毎回反転するかを調べる。床関数で写した座標の差を式にしてから色を定める。色が同じことは頂点を同一視してよい理由にはならず、元の選択肢は保つ。
問題固有の要素
縦横を交換した二種類の移動があるため、行の偶奇だけで足りるのは割った移動量が両方奇数の場合である。一方だけ奇数なら、行列和の偶奇を使うことで交換後の移動も同時に扱える。「通常の市松模様が失敗した」段階で二部性を諦めず、共通因子を除いた変位で色の反転を調べ直すのが本問の着眼点となる。
正当性
各空きマスを頂点とし、攻撃し合う二マスを漏れなく辺で結ぶ。合法な配置では辺の両端を同時に選ばないため、選んだ頂点は独立集合である。逆に独立集合の各マスへ一つずつコマを置けば、壁や攻撃に関する制約をすべて満たす。従って配置の最大化と独立集合の最大化は同値である。
任意の攻撃辺では、床関数で写した座標の差が または となる。 より両方が偶数となることはない。両奇なら行座標の差が奇数、一方だけ奇なら行列和の差が奇数なので、定義した色は必ず反転する。壁を除いてもこの性質は保たれ、競合グラフは二部グラフである。
最大matching後の交互路探索について、主単元の被覆復元より、 は大きさ の最小頂点被覆となる。被覆の補集合に辺の両端が残ることはなく、逆に独立集合の補集合は被覆である。よってその補集合 は大きさ の最大独立集合である。この集合だけを元の盤面上で o に変える手順は、最大個数に達する合法な配置を出力する。
実装上の注意
- でも 、 となり、行列和の色をそのまま使える。 の場合も含め、八方向の変位に重複が生じるため、変位を先に重複除去すると同じ攻撃辺を二重に保存せずに済む。
- 負方向もあるので、移動先の座標は符号付き整数で計算し、盤内か確認してから盤面を参照する。 など、移動先がすべて盤外となる場合も辺を張らない。途中のマスが壁かどうかは調べず、両端の空きマスだけを確認する。
- 交互路探索は最大matchingを確定した後、訪問状態を初期化して行う。最大化の途中の訪問印を流用せず、未使用の左頂点をすべて始点にする。matching辺かどうかは
mate で判定する。
- 全壁なら で、盤面をそのまま出す。孤立点は左なら探索の始点、右なら未到達なので、どちらも選ばれる。辺が一本もなければ全空きマスを
o にする。
復習の核
- 配置の最大化では、同時に選べない二要素を辺へ翻訳し、二部性を証明できるか調べる。
- 変位に共通因子があるときは、尺度を変えた座標の差を先に計算する。「同じ色」と「同じ頂点」を混同しない。
- 最大matchingの個数から最大独立集合の個数が分かっても、配置出力には被覆の復元が要る。未使用の左頂点からの交互路と、左は到達・右は未到達を選ぶ規則を対応させる。
計算量と制約
時間
を重複を除いた無向攻撃辺の数とする。盤面走査に 、彩色と各空きマスの高々八方向の辺生成に かかり、各頂点の次数は高々8なので である。Hopcroft–Karp法、またはこの二部matching用の単位容量ネットワークでのDinic法に 、交互路からの復元に 、盤面出力に 。全体で 時間、 より となる。この評価は や でも盤面走査・出力の時間を含む。
空間
入力・出力の盤面と座標から頂点IDへの対応が 、隣接リストが 、matchingの相手・到達状態・キューが 。全体で 空間となる。最大流を使う場合の逆辺と始点・終点もこの範囲に収まる。
制約との対応
、、。空きマスは最大 個、攻撃辺は最大 本なので、疎な二部グラフとして扱う。 は と、自己ループが生じないことを保証する。盤面は . と # からなり、出力は選んだ空きマスだけを o にした長さ の文字列を 行とする。時間制限は3秒、メモリ制限は1024 MiBであり、単純な一頂点ずつのDFS増加法の ではなく、上の評価を持つ最大matchingアルゴリズムを用いる。
出典