「AOJ0120 Patisserie」の編集履歴（バックアップ）一覧に戻る
*AOJ0120 Patisserie
**サイト
[http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0120]
**解説
n<=12なのでビットDPができる。そこで以下の2つの解法を示す。
+巡回セールスマン問題(TSP)
+BitDP + メモ化再帰
***解法: TSP
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度限りずつたどる」（巡回セールスマン問題(TSP)）
||<
よって巡回セールスマン問題を解くことに帰着する。ケーキの個数は12個以下と少ないのでこの解法でよいと裏付けができる。
ただし一つ注意すべきことがあって、箱の両端に置くケーキについては他の円のように片側が別の円と接していないことがある。
これに対し両端の余った幅はTSPと別枠で処理するやり方もあるが、ノードをもう一つ追加して、そのノードの円との幅は必ず接する円の半径に等しいと決めてやると蟻本の通りのTSPをそのまま適用できるので楽。TSPの解説は蟻本を見てください。
***解法: メモ化再帰
（編集中）
