UnKoder #06 : Infinite Network

あまり自信がないけど、一発ACで良かった。
https://www.hackerrank.com/contests/unkoder-06/challenges/infinite-network

問題

無限に広がる2次元座標において、座標の差が1の格子点同士の間がすべて線でつながっているとする。

ここでN個の格子点(以下代表点とする)の座標が与えられる。
幾つかの線を切断し、代表点がそれぞれ無限の数の格子点と線で連結しないようにしたい。
切断すべき最小の線の数を求めよ。

解法

以下の解法はBitDP解。グラフの最小カットにする解法もあるようだ。

いくつか代表点があった場合、それらが無限の数の格子点と連結しないようにするには以下のどちらかが考えられる。

• 全代表点を囲む最小の長方形を考え、それが外部の格子点と連結しないよう周囲の線を切断する。
• 全代表点を幾つかの点の集合に分割し、個々を再帰的に無限の数の格子点と連結しないようにする。

前者は、全代表店を囲む長方形を求めればよい。
後者はbitDPで分割パターンを列挙し、分割パターンの切断数の総和を最小化すればよい。

以下のコードはBitDPパートが余り賢くないので、0.94sと結構危ない。

int N;
int X[20],Y[20];
int dp[1<<16];
int mi=64;

int dodo(int mask) {
	int i;
	int L=1010,R=-1010;
	int T=1010,B=-1010;
	FOR(i,N) if(mask&(1<<i)) {
		L=min(L,X[i]);
		R=max(R,X[i]);
		T=min(T,Y[i]);
		B=max(B,Y[i]);
	}
	return min(64, 2*((R-L+1)+(B-T+1)));
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	int mask2;
	
	cin>>N;
	FOR(i,N) cin>>X[i]>>Y[i];
	FOR(i,1<<N) dp[i]=10000;
	dp[0]=0;
	for(int mask=1;mask<1<<N;mask++) {
		dp[mask]=dodo(mask);
		int d=__builtin_popcount(mask);
		if(d<=1) continue;
		
		vector<int> v;
		FOR(i,N) if(mask&(1<<i)) v.push_back(i);
		FOR(mask2,1<<(d-1)) {
			int mask22=0;
			FOR(i,d) if(mask2&(1<<i)) mask22|=1<<v[i];
			dp[mask]=min(dp[mask],dp[mask22] + dp[mask ^ mask22]);
		}
	}
	cout<<dp[(1<<N)-1]<<endl;
}

まとめ

最初1.94sで通ってびっくり。
これはO(N*3^N)だけど、O(N^2*2^N)位で通る解もあるのかな。