考察
domino の集合は grid graph の matching であり、覆われたセル値の総和は選んだ各辺の端点値和の総和に一致する。よって未被覆得点最大化は matching 辺重み和の最小化である。grid graph は checkerboard 色で二部グラフになる。matching size k ごとの最小費用 f(k) を min-cost flow の流量 k の最小費用として求められる。全辺重みに C を加えた size k matching の費用を f_C(k) とすれば、元の費用は厳密に f_C(k)-Ck。shift 後の非負費用で標準 min-cost flow を使える。domino を0枚置く場合も候補なので k=0 の費用0を含めて最小化し、答えは全セル総和からその最小被覆和を引く。
採用する候補: 辺重みを定数 C だけ非負へ shift した二部 matching の min_cost_slope を求め、全流量 k から元費用 f_C(k)-Ck の最小を選ぶ
任意個の domino を許すため matching size も最適化する。source→黒、隣接辺、白→sink を容量1で結べば matching と整数 flow が一対一に対応する。
棄却する候補: 負の端点和をもつ隣接 pair を重みの小さい順に貪欲選択する
一辺を選ぶと両端に接する複数辺が使えなくなるため局所最小は全体最小 matching を保証せず、cardinality 間の比較も必要である。
各セルを parity で左右に分け、source→片側と他側→sink に容量1・費用0、隣接セル辺に容量1・費用 A_u+A_v+C を張る。min_cost_slope の各流量候補で shiftedCost-C·k を評価し、その最小を totalSum から引く。
典型の発動条件
二部 matching の最小費用流帰着
発動条件: 二部グラフで互いに端点を共有しない辺集合の重み和を cardinality ごとに最小化するとき。
各頂点容量を1にした source-left-right-sink network を作る。
コストの一様 shift
発動条件: 負辺を含む固定 cardinality 最適化を、非負コストを要求する実装へ渡したいとき。
全辺へ C を足し、flow k の結果から Ck を引いて元費用へ戻す。
min_cost_slope
発動条件: 最適な flow 量自体も選ぶ必要があるとき。
0 から最大 matching size までの費用曲線を求め、補正後の最小点を選ぶ。
問題固有の要素
未被覆和を最大化する問題では、総和を定数として「覆う二セルの和」を最小化する matching に反転すると、負のセルも自然に扱える。
別の問題へ持ち帰る視点: 選択されなかった頂点重みの最大化は、選択辺が頂点素なら総頂点重みから matching の端点和を引く形を検討する。
正当性
dominoは隣接二セルmatchingでvertex容量1が重なり禁止。残る値総和はtotal−matching edge和なので任意matching濃度で辺和を最小にすればよい。shift CはkCだけ費用へ加えるため各flow kから引いて比較すると元目的を厳密に復元する。
実装上の注意
- C は全 A_u+A_v+C が非負になる値を選ぶ。総和・費用・Ck は 64 bit を使い、slope が区間を圧縮して返す実装では各線形区間の端点で補正値を評価する。
復習の核
- 1×1、1×2、全正、全負、負の辺同士が一セルを奪い合う小 grid を全 matching 列挙と比較し、k=0 と shift 補正を確認する。
計算量と制約
時間
盤面V=HW、隣接E=O(V)、最大domino数K≤V/2。min-cost slope with potentials O(K E log V)。
空間
残余graph、値、slope列 O(V)。
制約との対応
公式制約の確認範囲: Time limit: 2 sec; Memory limit: 1024 MiB; Constraints: 1\leq H; 1\leq W; HW\leq2000; -10 ^ {12}\leq A _ {i,j}\leq10 ^ {12}\ (1\leq i\leq H,1\leq j\leq W); All input values are integers.
出典