TopCoder SRM 579 Div2 Hard MarblePositioning

Div2 Hard、今回は珍しくさっくり解けた。
http://community.topcoder.com/stat?c=problem_statement&pm=12324

問題

R個の円盤があり、それぞれの半径が与えられる。
ここで、各円盤を下線の上に並べて置くようにする。
もちろん円盤同士は重なることができないが、円盤の並び順は任意である。

左端の円盤と右端の円盤の、接地部分同士の最短距離を求めよ。

解法

R<=8と数が小さいので、R!通り並び順を列挙していけばよい。

R個の円盤を左から順に並べていく場合、円盤の位置はすでに置いた円盤と接する位置のうち最も右になる。
半径AとBの円盤の間の距離はになるので、i番目の円盤の半径R_iと設置位置X_iに対しp番目の円盤位置はとなる。

よって計算量はO(R^2 R!)。R<=8なら問題ない。

class MarblePositioning {
	int stack[8];
	vector<int> R;
	public:
	
	double dist(double A,double B) {
		return sqrt((A+B)*(A+B)-(A-B)*(A-B));
	}
	
	double comp() {
		int i,j;
		vector<double> X(R.size(),0);
		
		for(i=1;i<R.size();i++) {
			FOR(j,i) X[i]=max(X[i],X[j]+dist(R[stack[i]],R[stack[j]]));
		}
		return X[R.size()-1];
	}
	
	double dfs(int cur,int mask) {
		int i;
		if(cur==R.size()) return comp();
		double mi=1e11;
		FOR(i,R.size()) {
			if(mask & (1<<i)) continue;
			stack[cur]=i;
			mi=min(mi,dfs(cur+1,mask | (1<<i)));
		}
		return mi;
	}
	
	double totalWidth(vector <int> radius) {
		R=radius;
		return dfs(0,0);
	}
};

まとめ

R<=8ということで全通りチェックはピンときた。
ここらへんの数値がヒントになることは時々あるな。

• N=8 : O(N^2 N!)ぐらい
• N=10 : O(N!)ぐらい、ここらまでが並べ替え全列挙の対象
• N=16 : O(N^2×2^N)ぐらい、さっきのDiv1 Medium
• N=20 : O(2^N)～O(N×2^N)ぐらい、ここらまでがBitDPの対象
• N=100 : O(N^3)
• N=1000 : O(N^2)
• N=10^6 : O(N logN)
• N=10^9 : O(N)
• N=10^12 : O(√N)
• N=10^16 : O(logN)