http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0120
n<=12なのでビットDPができる。そこで以下の2つの解法を示す。
2円が接して並んでいるとき、それぞれの中心から床に垂線を下ろして、垂線間の距離を取って円と円の幅のようなものを得る。図に描くと分かるが三平方の定理より
√{(r1+r2)^2-(r1-r2)^2}
で求まる。すべての2円間でこの距離を求めておき、あとは「うまく円を並べることにより距離の和が最小」になるようできれば与えられた直方体の幅と比較できる。この問いに答えれば解けるがどうすれば可能であるか。
円がA, B, C, D, Eと5つある時のことを考えよう。Aを固定してこれと接する円を考えて、求まった長さを図で列挙してみると
AとB ----- AとC --------- AとD --- AとE --------
のようになる。書き方を変えて
A ----- B A --------- C A --- D A -------- E
としてみる。B, C, D, Eそれぞれについても同様に考えて上図のようなものをつくり、それら全て集めてつなげるとグラフが出来る。円A, B, C, D, Eがノードになって自分以外のノード全てとつながるグラフとなっている。
問題がグラフに落とし込めたので、問いに答えうるように何らかのアルゴリズムが適用できないか推測すると
「コストの総和が最小となるように各ノードを1度限りずつ辿る」
というような問題に元の問題はほとんど言い換えらる。
よって巡回セールスマン問題を解く。ケーキの個数は12個以下と少ないのでこの解法で良さそうだと思える。
しかしここで箱の両端に置くケーキについて、それぞれ1つだけしか他のケーキと隣り合っていない問題が生じる。これではそのままTSPを適用できないので何らかの工夫が必要となる。
これに対し解決策は色々ありそうだが、うまいやり方としては、ノードをもう一つ追加して「追加したノードの円と接する円との幅は必ず接する円の半径に等しい」と決めてものが良い。
すると完全にTSPをそのまま適用するだけの問題となるので楽に解くことが出来る。
（編集中）
