TopCoder SRM 457 Div1 Hard TheSquareDivOne

問題

n x nマスの盤の上にいくつかコマが乗っている。
コマの乗っているマスは'C'であり、乗っていないマスは'.'で与えられる。

初期状態において、i行目に置かれているコマの数をrow[i]とする。
コマを、一つ選び、上下左右の空いているマスへ移動させるという操作を行って、
i列目に置かれているコマの数をrow[i]になるようにしたい。

操作の回数が最小となるような移動方法の、
移動後のコマの配置を出力せよ。そのような移動方法が複数ある場合、辞書順で最小のものを求めよ。

制約条件

n≦18

方針

まずは移動回数の最小値を求めることを考える。

これは、コマに区別がないことから、
各マスを頂点とし、隣接するマスをコスト1、容量無限の辺でつなぎ、
ソースから初期状態でコマの置かれているマスへコスト0、容量1の辺を張り、
終了状態でコマの置かれているマスからその列に対応する頂点へ、コスト0容量1の辺を張ったようなグラフにおける、
最小費用最大流のコストが移動回数の最小値になる。

次に辞書順最小をどうするかであるが、
前のMediumにあったように、左上から1マスずつ確定させて、
その度に費用流を流すような解法だと、費用流を18 * 18回流すことになり、2秒にぜんぜん間に合わない。

(0, 0)の頂点から列への辺のコストに移動コストに比べて十分小さい重みwを加え、
(0, 1)の頂点から列への辺のコストにw / 2を加え、
(0, 2)の頂点から列への辺のコストにw / 2 ^ 2を加え……
というふうにw * 2 ^ -kのコストを加えることを考える。

これは、正しいのだけれど、マスが18 * 18個あって、精度が足りなくなる。
なので、2列ぶんくらいずつだけをまとめて処理する。

1列ずつしかまとめないで処理したらTLEだった。

一度確定した'C'や'.'のマスは、
'.'だったら列の頂点に辺を結ばないように、
'C'だったら列の頂点への流量の下限を1に（蟻本の最大流のところのテクニック）して処理する。

ソースコード

const int dy[] = {-1, 0, 1, 0}, dx[] = {0, -1, 0, 1};
int n;
vector<string> board, ans;

void calc(){
	const ll COST = 1ll << 45;
	int row[50] = {}, cnt = 0;
	
	costflowGraph<ll> g(n * n + n + 2);
	int s = n * n + n, t = s + 1;
	
	rep(i, n) rep(j, n){
		if(board[i][j] == 'C') row[i]++, cnt++;
		rep(d, 4){
			int y = i + dy[d], x = j + dx[d];
			if(y < 0 || x < 0 || y >= n || x >= n) continue;
			g.add(i * n + j, y * n + x, 1000, COST);
		}
	}
	
	int num = 2 * n;
	rep(i, n) rep(j, n) if(ans[i][j] == '#'){
		ans[i][j] = '!';
		g.add(i * n + j, n * n + j, 1, 1ll << num);
		
		if(--num == 0) goto OUT;
	}
	OUT:
	rep(i, n) g.add(n * n + i, t, row[i], 0);
	
	rep(i, n) rep(j, n){
		if(board[i][j] == 'C') g.add(s, i * n + j, 1, 0);
		if(ans[i][j] == 'C'){
			g.add(s, n * n + j, 1, 0);
			g.add(i * n + j, t, 1, 0);
			cnt++;
		}
		else if(ans[i][j] == '#') g.add(i * n + j, n * n + j, 1, 0);
	}
	
	ll tmp = g.min_cost_flow(s, t, cnt);
	rep(i, n) rep(j, g.G[n * n + i].size()){
		
		costflowGraph<ll>::edge e = g.G[n * n + i][j];
		int y = e.to / n, x = e.to % n;
		if(e.cap <= 0 || y >= n || ans[y][x] != '!') continue;
		ans[y][x] = 'C';
	}
	rep(i, n) rep(j, n) if(ans[i][j] == '!') ans[i][j] = '.';
	
}

class TheSquareDivOne {
	public:
	vector <string> solve(vector <string> board) 
	{
		::board = board;
		n = board.size();
		ans = vector<string>(n, string(n, '#'));
		
		for(int cnt = 0; cnt < n * n; cnt += 2 * n) calc();
		return ans;
	}
};