読者です 読者をやめる 読者になる 読者になる

n-knuu's logs

憧れ駆動。だいたい競プロ

AOJ0120 Patisserie

bitDP AOJ

解法

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

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くらい)
幾何っぽい簡単な解法があるっぽい。

最後に

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