「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度限りずつ辿る」
||<
と元の問題は言い換えられる。
よって巡回セールスマン問題を解くことに帰着する。ケーキの個数は12個以下と少ないのでこの解法でよいと裏付けができる。
ただし一つ注意すべきことがあって、箱の両端に置くケーキについては他の円のように片側が別の円と接していないことがある。
これに対し両端の余った幅はTSPと別枠で処理するやり方もあるが、ノードをもう一つ追加して、そのノードの円との幅は必ず接する円の半径に等しいと決めてやると蟻本の通りのTSPをそのまま適用できるので楽。TSPの解説は蟻本を見てください。
***解法: メモ化再帰
（編集中）
*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度限りずつ辿る」
||<
というような問題に元の問題はほとんど言い換えらる。
よって巡回セールスマン問題を解く。ケーキの個数は12個以下と少ないのでこの解法で良さそうだと思える。
しかしここで箱の両端に置くケーキについて、それぞれ1つだけしか他のケーキと隣り合っていない問題が生じる。これではそのままTSPを適用できないので何らかの工夫が必要となる。
これに対し解決策は色々ありそうだが、うまいやり方としては、ノードをもう一つ追加して「追加したノードの円と接する円との幅は必ず接する円の半径に等しい」と決めてものが良い。
すると完全にTSPをそのまま適用するだけの問題となるので楽に解くことが出来る。
***解法: メモ化再帰
（編集中）
