Patisserie(AOJ No.0120)

半径 $r_i$ の丸いロールケーキが $n$ 個ある( $r_1, r_2, \cdots , r_n$ )。
これを長さ $l$ の箱に入れることができるかを答える。
ただし、ロールケーキは箱の底面に接しておき、重ねておくことができない。
また、ロールケーキとロールケーキの間の隙間に小さいロールケーキが入ることはない
(隣り合うロールケーキがある一点で接するように置く)。
制約
$0 < n\leq 12$
$3\leq r_i \leq 10$

アルゴリズム

ごり押ししようとすると、 $12! = 479,001,600$ 通り調べることになるが、もしかすると、Cとかなら通る？
今回は、巡回セールスマン問題に落とし込んで解く。
半径 $r_i$ のケーキの中心から、半径 $r_j$ のケーキの中心までのx方向の距離をエッジの重み $d(i,j)$ と考える。
２円の中心を結ぶ線を斜辺とする直角三角形を考えると、 $d(i,j) = \sqrt{(r_i + r_j)^2 - (r_i - r_j)^2}$
左端の円と右端の円の半径分の長さも考慮するのを忘れないようにする。
スタートノード(最後に戻ってくるノード)を0として、
$d(0,j) = r_j, d(i,0) = r_i$ という風に重み付けし、
0から始まって、巡回し、0に戻ってくるまでの最小距離が $l$ より大きいかどうかをみれば、答えが求まる。
これをビットDPで解けば計算量は $O(2^n n^2)\rightarrow 2^{13} 13^2 = 8192\times 169 = 1,384,448$ なので余裕だろう。

重み付けの仕方は、もっといろいろなやり方があるだろう。

コード

import java.util.*;
public class aoj0120 {
	static final Scanner stdin = new Scanner(System.in);
	static final double INF = 1e8;
	public static void main(String[] args) {
		while(stdin.hasNext()){
			String[] line = stdin.nextLine().split(" ");
			int l = Integer.parseInt(line[0]), n = line.length;
			int[] r = new int[n];
			r[0] = 0;
			for(int i = 1; i < n; ++i) r[i] = Integer.parseInt(line[i]);
			double[][] d = new double[n][n];
			for(int i = 0; i < n; ++i)
				for(int j = 0; j < n; ++j)
					d[i][j] = (i == j ) ? 0 : 
						(i == 0) ? r[j] : 
						(j == 0) ? r[i] : 
						Math.sqrt(Math.pow(r[i] + r[j], 2) - Math.pow(r[i] - r[j], 2));
			System.out.println(TSP(d,0).getLength() <= l ? "OK" : "NA");
		}
	}
	@SuppressWarnings("unused") public static class TSPResult{
		private int s;		//source node (※= destination node)
		private double length;	//length of shortest Hamilton cycle
		private int[][] prev;	//back pointers
		public TSPResult(int s, double length, int[][] prev){ set(s, length, prev); }
		final private void set(int s, double length, int[][] prev){ this.s = s; this.length = length; this.prev = prev; }
		final public double getLength(){ return length; }
	}
	static TSPResult TSP(double[][] G, int s){
		int n = G.length, N = 1 << n;
		double[][] DP = new double[N][n];
		int[][] prev = new int[N][n];
		for(int i = 0; i < N; ++i) Arrays.fill(DP[i], INF);
		for(int i = 0; i < n; ++i){
			DP[1<<i][i] = G[s][i];
			prev[1<<i][i] = s;
		}
		for (int S = 1; S < N; ++S) {
			for (int i = 0; i < n; ++i) {
				if ((S & (1<<i)) == 0) continue;
				for (int j = 0; j < n; ++j) {
					if ((S & (1<<j)) != 0 ) continue;
					//i in S, j not in S 
					double newDist = DP[S][i]+G[i][j];
					if(DP[S|(1<<j)][j] > newDist) {
						DP[S|(1<<j)][j] = newDist;
						prev[S|(1<<j)][j] = i;
					}
				}
			}
		} 
		return new TSPResult(s, DP[N-1][s], prev);
	}
}