GCJ2008 WF E: The Year of Code Jam

蟻本

蟻本の一番最後に載っている問題。
最終的には蟻本と同じになるのだけど、前回の記事で書いた方法でより機械的に解いてみる。
まず前段階として、問題のサイズはそんな大きくないし、基本的には?の部分を開催するかどうかという2択から選ぶのだから最小カットで行けそうだと信じることが前提。部分問題に落とすのも辛そうなのでDPも上手く行かなそうだし…。

方針

x[i] = {i番目の日にコンテストを開く?1:0}
としてみる(とても自然)。
今回は最大化の問題なので、例によって損害を最小化する問題だと考える。基本的には毎日コンテストを開いて幸福度4を得られたものだと考えてみる。
このとき、最小化すべき損害の式(目的関数)は次のようになる。長くなるので4つに分ける。

  • sum f(x[i])*0 + f(1-x[i])*4

コンテストを開かなかったら損害4が発生する。

  • sum_{i,jは隣接している} f(x[i]+x[j]-1)*2

x[i]=x[j]=1のときは2の損害を受ける。

  • sum_{i日目はコンテストが無いと確定している} f(x[i])*inf

x[i]=1のときinfのペナルティを受けると思えば良い。

  • sum_{i日目はコンテストが有ると確定している} f(1-x[i])*inf

x[i]=0のときinfのペナルティを受けると思えば良い。

ここまではx[i]を上の様に定義したら勝手に出てくる。
さて、2つ目の式ではfの中に差分でないf(x[i]+x[j]-1)が出ている。このままでは最小カットにならないので、この形の常套手段としてx[j]=1-x[j]と置き換えてみる。つまり、二部グラフの片側に属する頂点に対しては
x[i] = {i番目の日にコンテストを開く?0:1}
と入れ替えることにする。f(x[i]+x[j]-1)と書いている部分の、iとjは二部グラフのことなる成分に属しているので今回はこれでfの中身を全部差分にできる。後は1,3,4つ目の目的関数についても二部グラフの片方についてx[i]と1-x[i]を入れ替えてやれば良い。
ということで、この問題で二部グラフの片側について0,1を入れ替えるのは極めて自然で、特別な発想を要するものではないことであったことがわかった(もちろん実際にコンテスト中に気づけるかは別問題だけど、少なくとも冷静な状態だとそんな突飛ではない)。
結局、x[i](=x[i]-0)か1-x[i]かx[i]-x[j]という差分の形を作ることを目標にすればよいだけだった。

acceptされたコード

int toIndex(int y, int x) {
	return y * W + x;
}

int solve() {
	Graph G;
	G.init(H*W + 2);
	const int s = H*W, t = s + 1;

	for (int y = 0; y < H; ++y) {
		for (int x = 0; x < W; ++x) {
			if ((y+x)%2 == 0) {
				G.addDirectedEdge(s, toIndex(y, x), 4);
				for (int k = 0; k < 4; ++k) {
					const int ny = y + dy[k], nx = x + dx[k];
					if ( 0 <= ny && ny < H && 0 <= nx && nx < W ) {
						G.addDirectedEdge(toIndex(y,x), toIndex(ny,nx), 2);
					}
				}
				if (board[y][x] == '.') {
					G.addDirectedEdge(toIndex(y, x), t, INF);
				}
				else if (board[y][x] == '#') {
					G.addDirectedEdge(s, toIndex(y, x), INF);
				}
			}
			else {
				G.addDirectedEdge(toIndex(y, x), t, 4);
				if (board[y][x] == '.') {
					G.addDirectedEdge(s, toIndex(y, x), INF);
				}
				else if (board[y][x] == '#') {
					G.addDirectedEdge(toIndex(y, x), t, INF);
				}
			}
		}
	}

	return 4 * H * W - calcMaxFlow(G, s, t);
}