G - Grid Coloring 2 Editorial by MMNMM
まず、\(B _ {i,j}\) に \(0\) が含まれないとしてよいです（含まれた場合、その \(0\) をすべて \(1\) に変えることでコストが増加しないことが示せます）。
この問題は、次のような形で書くことができます。
\[\min _ {B\in\lbrace{1,2,3,4,5}\rbrace ^ {\lbrace1,2,\ldots,N\rbrace ^ 2}}\sum _ x\theta _ x(B _ x)+\sum _ {x\lt y}\phi _ {x,y}(B _ x,B _ y)\]
ただし、
- \(x,y\) は \(\lbrace1,2,\ldots,N\rbrace ^ 2\) をわたり、不等号 \(x\lt y\) は辞書順で \(x\) が \(y\) より小さいことを表す。
- \(x=(i,j)\) について \[\theta _ x(b)=\begin{cases}0&\quad(A _ {i,j}=0\vee b = A _ {i,j})\\+\infty&\quad(\text{otherwise.})\end{cases}\]
- \(x=(i,j),y=(k,l)\) について \[\phi _ {x,y}(b _ 1,b _ 2)=\begin{cases}0&\quad(\vert i-k\vert+\vert j-l\vert\neq1)\\ (b _ 1-b _ 2) ^ 2&\quad(\text{otherwise.})\end{cases}\]
とします。
すると、任意の \(x,y\) について \(\phi _ {x,y}\) が monge であるので、この最小化問題は最小カットを用いて解くことができます。
（いわゆる「燃やす埋める問題」の \(k\) 値への一般化です。詳しくは tokoharu-sakuraさんの記事やnoshi91さんの記事が参考になります。）
グラフの具体的な構築
\(x _ {\gt k}\ (x\in\lbrace1,2,\ldots,N\rbrace ^ 2,k=1,2,3,4)\) および \(s,t\) の \(4N ^ 2+2\) 頂点を作り、次のような辺を貼ります。
- すべての \(x\in\lbrace1,2,\ldots,N\rbrace ^ 2\) について \(x _ {\gt k+1}\to x _ {\gt k}\ (1\leq k\lt4)\) 、重み \(+\infty\)
- \(A _ x\neq 0\) であるような \(x\) について
- \(1\lt A _ x\) ならば \(s\to x _ {\gt A _ x-1}\) 、重み \(+\infty\)
- \(A _ x\lt 5\) ならば \(x _ {\gt A _ x}\to t\) 、重み \(+\infty\)
- 隣接するマス \(x,y\) について
- \(x _ k\to y _ k\ (1\leq k\leq 4)\) 、重み \(1\)
- \(x _ k\to y _ l\ (1\leq l\lt k\leq 4)\) 、重み \(2\)
このグラフにおける \(s–t\) 最小カットが最適解に、カットの重みがそのときのコストに対応しています。
まず、最小カットに重み \(+\infty\) の辺が含まれないことを示します。
証明
\(B _ x=\begin{cases}A _ x&\quad(A _ x\neq 0)\\1&\quad(A _ x=0)\end{cases}\) とし、\(B _ x\gt k\) のときかつそのときに限り \(x _ {\gt k}\) を \(s–t\) カットの \(s\) 側の頂点とします。 すると、このカットの重みは有限であることが確かめられるので、\(+\infty\) の辺が含まれるカットは最小カットにならないことがわかります。
問題の条件がグラフで表現されていることを確認します。
条件 1: \(B _ x\in\lbrace1,2,3,4,5\rbrace\)
まず、\(1\) 種類目の辺によって、最小カットにおいて \((i,j) _ {\gt k}\) のうちどの頂点が \(s\) 側に属するかが \(5\) 通りに制限されます。
よって、上の図のように \((i,j) _ {\gt k}\) のうち \(s\) 側にある頂点によって \(B _ {i,j}\) の値を定めることができます。
条件 2: \(A _ x\neq0\implies A _ x=B _ x\)
\(2\) 種類目の辺を張ることで \(B _ x\leq A _ x-1\) および \(B _ x\gt A _ x\) を禁止することができ、\(A _ x\neq0\implies A _ x=B _ x\) が表現できます。
条件 3: コストが \((B _ x-B _ y) ^ 2\)
\(3\) 種類目の辺では、隣接するマス \(x,y\) について \(x _ {\gt k},y _ {\gt k}\) 間に張られている辺の寄与が \((B _ x-B _ y)^2\) と等しくなります。
\(1+3+\cdots+(2k+1)=k ^ 2\) を利用しています。
よって、このグラフの \(s–t\) 最小カットを求めることでこの問題を解くことができます。
書き込める整数を \(0,1,\ldots,d\) として、グラフの頂点数は \((d-1)N ^ 2+2\) 、辺数はたかだか \((2d^2-3d+2)N ^ 2-(2d^2-4d+2)N\) 本です（すでに値の決まっているマスに関する頂点を作らないことで削減することができますが、最悪時のオーダーは変化しません）。 最大流がたかだか \(2(d-1)^2N(N-1)\) なので、辺容量が整数の Dinic の計算量 \(O(Fm)\) によって全体の計算量が \(O(d^4N^4)\) でおさえられます。
この問題では \(d=5,N\leq20\) なので、十分高速です。
実装例は以下のようになります。
#include <iostream>
#include <atcoder/maxflow>
int main() {
using namespace std;
unsigned N;
cin >> N;
atcoder::mf_graph<int> G(1 + 4 * N * N + 1);
// S-T カットに帰着
const unsigned S = 0, T = 1 + 4 * N * N;
// 条件「マス (i, j) の値が v より大きい」に対応する頂点番号を返す関数
const auto index{[N](unsigned i, unsigned j, unsigned v){ return (i * N + j) * 4 + v; }};
constexpr int inf = 2 * 20 * 19 * 16 + 1; // ありえるコストの最大値より大きい値を inf とする
for(unsigned i{}; i < N; ++i)
for(unsigned j{}; j < N; ++j)
for(unsigned v{1}; v + 1 <= 4; ++v)
// (i,j) が v+1 より大 ⟹ v より大 : v+1 が 1 かつ v が 0 ならペナルティ +∞
G.add_edge(index(i, j, v + 1), index(i, j, v), inf);
// 横のマスの差の二乗
for(unsigned i{}; i < N; ++i)
for(unsigned j{}; j + 1 < N; ++j)
for(unsigned v{1}; v <= 4; ++v){
G.add_edge(index(i, j, v), index(i, j + 1, v), 1);
G.add_edge(index(i, j + 1, v), index(i, j, v), 1);
for(unsigned u{1}; u < v; ++u){
G.add_edge(index(i, j, v), index(i, j + 1, u), 2);
G.add_edge(index(i, j + 1, v), index(i, j, u), 2);
}
}
// 縦のマスの差の二乗
for(unsigned i{}; i + 1 < N; ++i)
for(unsigned j{}; j < N; ++j)
for(unsigned v{1}; v <= 4; ++v){
G.add_edge(index(i, j, v), index(i + 1, j, v), 1);
G.add_edge(index(i + 1, j, v), index(i, j, v), 1);
for(unsigned u{1}; u < v; ++u){
G.add_edge(index(i, j, v), index(i + 1, j, u), 2);
G.add_edge(index(i + 1, j, v), index(i, j, u), 2);
}
}
// すでに書き込まれているマス
for(unsigned i{}; i < N; ++i)
for(unsigned j{}; j < N; ++j){
unsigned A;
cin >> A;
if(A == 0)
continue;
if(A < 5)
G.add_edge(index(i, j, A), T, inf);
if(A > 1)
G.add_edge(S, index(i, j, A - 1), inf);
}
// S から T までフローを流し、最小カットを求める
G.flow(S, T);
const auto& cut{G.min_cut(S)};
for(unsigned i{}; i < N; ++i){
for(unsigned j{}; j < N; ++j){
unsigned B{1};
for(unsigned v{1}; v <= 4; ++v)
B += cut[index(i, j, v)];
cout << B << " ";
}
cout << endl;
}
return 0;
}
posted:
last update: