AOJ0120 Patisserie - n-knuu's logs

問題

解法

bitDPで解く(bitDPは蟻本中級編に載っている、蟻本を読もう！)

プログラミングコンテストチャレンジブック [第2版]　?問題解決のアルゴリズム活用力とコーディングテクニックを鍛える?

作者: 秋葉拓哉,岩田陽一,北川宜稔
出版社/メーカー: マイナビ出版
発売日: 2012/01/28
メディア: Kindle版
この商品を含むブログを見る

stateをN桁のビットとして、右からi桁目のビットをi番目のケーキ(の半径)とする。
このとき
dp[state][v] = 状態stateのとき(つまりビットが立っているケーキを既に詰めたとき)、v番目のケーキを最後に詰めた場合の使った長さの最小値
とする。
これをdp[state][u] = min{dp[state | 1 << u][u] + d[v, u], (state >> u & 1) == 0}と更新することで求める。
ただし、d[v, u]はケーキvとケーキuをくっつけて箱に詰めたときの、中心間の平行距離(下図において $\sqrt{(r1+r2)^2 - (r1-r2)^2}$ として求まる距離)である。
f:id:n_knuu:20151013193527p:plain

ただし、注意として、一番右と一番左のケーキについては、半径をそのまま足さないといけないことに注意する。これはstate==0のときと、state==(1 << N)-1のときはそのまま半径を足してやることにすればよい。
答えは、dp[0][0]が箱の大きさより小さいかどうかによって、OKかNAを出力すれば良い。
計算量は $O(N^2 2^N)$ である。最大ケースで $6*10^5$ くらい。

ソースコード

メモ化再帰で求めた。
C++で一行を取得する方法を知らないのでPythonで書いた。

感想

巡回セールスマン問題の応用。巡回セールスマンっぽいbitDPはライブラリにおいておいてもいい気がする。
Pythonで書くとTLギリギリだった。(TLがPythonだと5.00secで、04.46 sec)
ループで書くとTLEした(10secくらい)
幾何っぽい簡単な解法があるっぽい。

最後に

ほぼ日刊は難しい気がしてきている