kmjp's blog

競技プログラミング参加記です

TopCoderOpen 2016 Round2C Medium BearGridRect

SRM

そのテク忘れてた。
https://community.topcoder.com/stat?c=problem_statement&pm=14322

問題

N*Nのグリッドがある。
各列・各行それぞれ1個のセルにポーンの駒を置くようにしたい。

ここでM個の条件が与えられる。
各条件は互いに重ならない矩形の範囲(R1[i],C1[i])-(R2[i],C2[i])と、内部のポーンの数cnt[i]を示す。
条件を満たすポーンの配置が可能なら、それを答えよ。

解法

割当問題なのでグラフを使って解こう。
始点から行に対応するN点に容量1の辺を張り、列に対応するN点から終点に容量1の辺を張ろう。
あとは行に対応する点と列に対応する点の間にうまい辺を張ると、フローをN流す行と列の対応を求める問題にできる。

矩形同士は重ならないことから、各条件iに対し行R1[i]～R2[i]に対応する点から、条件毎に作成した点に容量１の辺を張り、さらにその点から別の１点に容量cnt[i]の辺を張り、その辺から列C1[i]～C2[i]に対応する点に辺を張ると、矩形の条件に対応する辺が張れる。
ただ、問題はそれ以外のどの矩形にも含まれないセルに対する条件である。
どの矩形にも含まれないセルには、N-sum(cnt[i])個のポーンを置きたいが、最大フロー問題ではこれに対応できない。

そこで最小コストフローを用いる。
どの矩形にも属さないセル(r,c)について行rに対応する点から列cに対応する点に容量１コスト１の辺を張ろう。
こうして最小コストフローを解くと、できるだけ条件に対応する辺が選択される。
この際、コストがN-sum(cnt[i])ぴったりでないなら、条件を満たす配置は出来ない。

コストがN-sum(cnt[i])ぴったりなら、あとはグラフの流量から逆算して行と列の対応関係を求めよう。

int id[51][51];

template<int NV,class V> class MinCostFlow {
public:
	struct edge { int to, capacity; V cost; int reve;};
	vector<edge> E[NV]; int prev_v[NV], prev_e[NV]; V dist[NV];
	void add_edge(int x,int y, int cap, V cost) {
		E[x].push_back((edge){y,cap,cost,(int)E[y].size()});
		E[y].push_back((edge){x,0, -cost,(int)E[x].size()-1}); /* rev edge */
	}
	
	V mincost(int from, int to, int flow) {
		V res=0; int i,v;
		ZERO(prev_v); ZERO(prev_e);
		while(flow>0) {
			fill(dist, dist+NV, numeric_limits<V>::max()/2);
			dist[from]=0;
			priority_queue<pair<int,int> > Q;
			Q.push(make_pair(0,from));
			while(Q.size()) {
				int d=-Q.top().first, cur=Q.top().second;
				Q.pop();
				if(dist[cur]!=d) continue;
				if(d==numeric_limits<V>::max()/2) break;
				FOR(i,E[cur].size()) {
					edge &e=E[cur][i];
					if(e.capacity>0 && dist[e.to]>d+e.cost) {
						dist[e.to]=d+e.cost;
						prev_v[e.to]=cur;
						prev_e[e.to]=i;
						Q.push(make_pair(-dist[e.to],e.to));
					}
				}
			}
			
			if(dist[to]==numeric_limits<V>::max()/2) return -1;
			int lc=flow;
			for(v=to;v!=from;v=prev_v[v]) lc = min(lc, E[prev_v[v]][prev_e[v]].capacity);
			flow -= lc;
			res += lc*dist[to];
			for(v=to;v!=from;v=prev_v[v]) {
				edge &e=E[prev_v[v]][prev_e[v]];
				e.capacity -= lc;
				E[v][e.reve].capacity += lc;
			}
		}
		return res;
	}
};

class BearGridRect {
	public:
	int M;
	vector <int> findPermutation(int N, vector <int> Y1, vector <int> Y2, vector <int> X1, vector <int> X2, vector <int> cnt) {
		MinCostFlow<600,int> mcf;
		
		M=Y1.size();
		int i,x,y;
		int sum=0;
		MINUS(id);
		FOR(i,M) {
			int h=Y2[i]-Y1[i]+1;
			int w=X2[i]-X1[i]+1;
			if(cnt[i]>min(h,w)) return {-1};
			sum+=cnt[i];
			for(y=Y1[i];y<=Y2[i];y++) for(x=X1[i];x<=X2[i];x++) id[y][x]=i;
		}
		
		FOR(y,N) mcf.add_edge(0,100+y,1,0);
		FOR(x,N) mcf.add_edge(400+x,500,1,0);
		
		FOR(i,M) {
			for(y=Y1[i];y<=Y2[i];y++) mcf.add_edge(100+y,200+i,1,0);
			mcf.add_edge(200+i,300+i,cnt[i],0);
			for(x=X1[i];x<=X2[i];x++) mcf.add_edge(300+i,400+x,1,0);
		}
		FOR(y,N) FOR(x,N) if(id[y][x]==-1) mcf.add_edge(100+y,400+x,1,1);
		
		int cost=mcf.mincost(0,500,N);
		if(cost==-1) return {-1};
		if(cost+sum!=N || sum>N) return {-1};
		
		vector<int> ret(N,0);
		vector<int> tmp[51];
		FOR(y,N) {
			int id=100+y;
			FORR(e,mcf.E[id]) if(e.capacity==0) {
				if(e.to>=200 && e.to<300) tmp[e.to-200].push_back(y);
				if(e.to>=400) ret[y]=e.to-400;
			}
		}
		FOR(x,N) {
			int id=400+x;
			FORR(e,mcf.E[id]) if(e.capacity==1 && e.to>=300 && e.to<400) {
				int rec=e.to-300;
				ret[tmp[rec].back()]=x;
				tmp[rec].pop_back();
			}
		}
		
		
		return ret;
	}
}

まとめ

本番フローには落とし込めたし、矩形条件までは思いつけたが、矩形外を最小コストフローで処理することは思いつかなかった…。