ABC193 F - Zebraness - かんプリンの学習記録

問題概要

${N×N}$ のマス目が白か黒に塗られており，塗られていないマスもある．塗られていないマスを白か黒で塗るとき，隣り合ったマスが異なる色で塗られているようなマスの組の数の最大値を求めよ．

${1\leq N\leq 100}$

隣り合ったマスに異なる色を塗った場合1点得るというように考える．

${\downarrow}$

以下の条件で利得の最大化を行うことになる.

${\downarrow}$

白/黒で塗るという選択と, 複数の選択の間に対する制約(罰則条件)があるのでProjectSelectionProblem(俗にいう燃やす埋める問題)を解くアルゴリズムを使えそう.
ProjectSelectionProblemについてはこちら

上の条件は利得になっているのでProjectSelectionProblemに対応させるため損失に書き直す.

隣り合ったマスの組の数からこれの解を引けば答えになる．また， ${i+j}$ が偶数のときと奇数のときで白/黒の選択を表す辺の並びを変える必要がある．

例として隣り合った「黒に塗られたマス」と「塗られていないマス」の状況をグラフで表すと以下のようになる. 頂点 ${A}$ が既に黒に塗られたマスを表し, 頂点 ${B}$ がまだ塗られていないマスを表す.

このグラフのSからTへの最大流が答え．容量0の辺はどうせ流れないので張らなくてもいい．

燃やす埋める問題に関する基礎知識は以下の記事を参考にしてください．
kanpurin.hatenablog.com

ProjectSelectionProblemの他の問題は以下にまとめています．
kanpurin.hatenablog.com

AtCoderでProjectSelectionProblemは解いたことなかった(忘れてるだけor精進足らず)のでおもしろかった．

追記
普通にありました．(ネタバレ回避のため載せませんが)