Official

O - グリッド最大化 / Grid Maximize Editorial by kyopro_friends

この問題は Project Selection Problem の特殊系、俗に燃やす埋める問題と呼ばれる問題に帰着することができます。

燃やす埋める問題

次のような問題を考えます。

\(N\) 個の真偽値変数 \(X_1,\ldots,X_N\) があり、これらに対して真または偽を割り当てる。次の3種類の形のいずれかの条件がいくつか与えられるので、コスト最小の割当とそのコストを求めよ。

  • \(X_{A_i}\) が真かつ \(X_{B_i}\) が偽ならば \(C_i\) のコストがかかる
  • \(X_i\) が真ならば \(T_i\) のコストがかかる
  • \(X_i\) が偽ならば \(F_i\) のコストがかかる

この問題に対して次の \(N+2\) 頂点のグラフ \(G\) を考えます。

  • 頂点のラベルを \(1,2,\ldots,N,T,F\) とする
  • \(A_i\) から\(B_i\) へ容量 \(C_i\) の辺を張る
  • \(i\) から \(F\) へ容量 \(T_i\) の辺を張る
  • \(T\) から \(i\) へ容量 \(F_i\) の辺を張る

グラフ \(G\) における \(T\)-\(F\) 最小カットが求めるものになります。\(G\) における \(T\)-\(F\) カットにおいて \(T\) と同じ側に属する頂点に対応する変数に真、\(F\) と同じ側に属する頂点に対応する変数に偽を割り当てることで、カットと \(X_i\) への真偽の割当が対応することから示せます。

元の問題

上から \(i\) 行目左から \(j\) 列目のマスをマス \((i,j)\) と表します。

まず問題を最小化に言い換えるため、全ての値 \(x\) を \(9-x\) に置き換えます。すなわち、問題を次の通り読み替えます。

  • グリッドに \(0\) 以上 \(9\) 以下の数を書き込み、書き込んだ数の総和を最小化せよ
  • 隣り合う2マスの和は\(18-D\) 以上でなければならない

読み替え後の問題を前半で扱ったような真偽値の割当問題に帰着するために以下の工夫が必要です。

工夫

整数変数の真偽値変数への読み替え

マスに書き込む数は整数値なので、このままでは真偽値の割当問題に帰着することができませんが「真偽値変数 \(X_{i,j,k}\) はマス \((i,j)\) に書かれた数が \(k\) 以上のとき真」のようにすることで（取りうる値の種類数を \(T\) として） \(O(T)\) 個の真偽値変数に読み替えることができます。

反転

全てのマスについて「真偽値変数 \(X_{i,j,k}\) はマス \((i,j)\) に書かれた数が \(k\) 以上のとき真」のように帰着すると、「隣り合うマスの和は \(18-D\) 以上でなければならない」という条件をうまく扱うことができません。ここで、マスの隣接関係がなすグラフは二部グラフであることから、次のように二部グラフの一方を反転することでうまくいきます。

  • \(i+j\) が偶数ならば「真偽値変数 \(X_{i,j,k}\) はマス \((i,j)\) に書かれた数が \(k\) 以上のとき真」
  • \(i+j\) が奇数ならば「真偽値変数 \(X_{i,j,k}\) はマス \((i,j)\) に書かれた数が \(k\) 以下のとき真」

こうすることで、「隣り合うマスの和は \(18-D\) 以上でなければならない」という条件は、\(i+j\) が奇数である全ての \((i,j,k)\) について

  • \(X_{i,j,k}\) が真かつ \(X_{i+1,j,(18-D)-k}\) が偽ならばコスト \(\infty\)

のような形で表せます。

まとめ

以上により、\(O(HWT)\) 個の真偽値変数に対して条件がついた問題とみなすことができ、適切なグラフを構築して最大流問題を解くことで答えを求めることができます。

計算量

グリッドに書き込む値の上限を \(T\) として、最大流量が \(O(HWT)\)、グラフの辺数が \(O(HWT)\) であることから、最大流を求めるための計算量は \(O(H^2W^2T^2)\) となります。

writer解(C++) 

#include<bits/stdc++.h>
#include<atcoder/maxflow>
using namespace std;
#define rep(i,l,r)for(int i=(l);i<(r);i++)

const int MAX=10;

int main(){
	int h,w,d;
	cin >> h >> w >> d;
	vector<vector<int>>a(h,vector<int>(w));
	rep(i,0,h)rep(j,0,w)cin >> a[i][j];
	//全部9から引いて最小化問題にする
	rep(i,0,h)rep(j,0,w)a[i][j]=MAX-1-a[i][j];
	
	//「xがtrueでyがfalseならコストc」→「x→yに容量c」
	//(i+j)%2==0のとき、「i,j,kは「(i,j)はk以上」
	//(i+j)%2==1のとき、「i,j,kは「(i,j)はk以下」
	int TRUE=h*w*MAX;
	int FALSE=h*w*MAX+1;
	vector<vector<unordered_map<int,int>>>idx(h,vector<unordered_map<int,int>>(w));
	rep(i,0,h)rep(j,0,w){
		if((i+j)%2==0){
			rep(k,-20,1)idx[i][j][k]=TRUE;
			rep(k,1,MAX)idx[i][j][k]=i*w*MAX+j*MAX+k;
			rep(k,MAX,30)idx[i][j][k]=FALSE;
		}else{
			rep(k,-20,0)idx[i][j][k]=FALSE;
			rep(k,0,MAX-1)idx[i][j][k]=i*w*MAX+j*MAX+k;
			rep(k,MAX-1,30)idx[i][j][k]=TRUE;
		}
	}
	
	const int INF=(int)1e9;
	atcoder::mf_graph<int>g(h*w*MAX+2);
	
	rep(i,0,h)rep(j,0,w){
		if((i+j)%2==0){
			rep(k,0,MAX)g.add_edge(idx[i][j][k+1],idx[i][j][k],INF);
			rep(k,1,MAX)g.add_edge(idx[i][j][k],FALSE,1);
			if(a[i][j]!=MAX){
				rep(k,0,a[i][j]+1)g.add_edge(TRUE,idx[i][j][k],INF);
				rep(k,a[i][j]+1,MAX)g.add_edge(idx[i][j][k],FALSE,INF);
			}
		}else{
			rep(k,0,MAX)g.add_edge(idx[i][j][k],idx[i][j][k+1],INF);
			rep(k,0,MAX-1)g.add_edge(TRUE,idx[i][j][k],1);
			if(a[i][j]!=MAX){
				rep(k,0,a[i][j])g.add_edge(idx[i][j][k],FALSE,INF);
				rep(k,a[i][j],MAX)g.add_edge(TRUE,idx[i][j][k],INF);
			}
		}
	}
	
	auto in=[&](int i,int j){return 0<=i&&i<h&&0<=j&&j<w;};
	
	//和を18-D以上にしたいので「x以下⇒(18-D-x)以上」
	vector<pair<int,int>>d4({{-1,0},{1,0},{0,-1},{0,1}});
	rep(i,0,h)for(int j=1-i%2;j<w;j+=2){
		for(auto[di,dj]:d4)if(in(i+di,j+dj)){
			int ii=i+di,jj=j+dj;
			rep(k,0,MAX)g.add_edge(idx[i][j][k],idx[ii][jj][2*(MAX-1)-d-k],INF);
		}
	}
	
	int flow=g.flow(TRUE,FALSE);
	int cnt=0;
	int sum=0;
	rep(i,0,h)rep(j,0,w){
		if(a[i][j]==MAX)cnt++;
		else sum+=a[i][j];
	}
	
	cout << ((MAX-1)*cnt)-(flow-sum) << endl;
}

余談

この問題は整数計画問題として定式化することができます。十分高速な整数計画問題ソルバーであれば、この問題を整数計画問題としてそのまま解くことができます。

posted:
last update: