Quest

原案: chokudai
解答: chokudai, hos
解説: chokudai
市場(0,0)における商品の売却価格p・重さw
と、N個の街のx座標,y座標、商品の購入価
格qが与えられる。
 移動にかかる時間は、移動する区間のマン
ハッタン距離に等しい。
 購入、売却は一瞬で行うことが可能。
 街を行き来して転売を行う事で、制限時間T
の間に可能な限り多く稼ぐ。


時間ごとに、「今持っている重さ」「今いる場
所」ごとの、最大の利益を持つ。


「買った瞬間に利益が得られるものと考えてしまえ
ば、このDPは可能となる。
この方法では、状態数がO(TNW)となり、これ
は間に合わない。

ある街の集合を全て回った時に、
全ての町をたどって市場に戻る最短距離は一定
 持てる重さが一定なので、得られる利益も一定



街の集合は2^N個しかない
よって、これを用いて時間ごとの利益がDPで
求めることが可能！

N個の街の部分集合の全ての最短経路

O(2^N * N^2)のDP （巡回セールスマン）


2^N個の部分集合の買い物で得られる利益


O(7!)とかO(7! * 2^N)とかで、全探索してもOK!
O(2^N * W * M)のDP （ナップサック）
街の集合を要素として、時間ごとの利益

O(T * 2^N)のDP （ナップサック）
よって、DPで全て解くことが可能
稼ぐ金額は、W * P * T /2で、10^12程度
 64bit変数を使用しないとオーバーフローして
しまう。

First submission: 185min (wakaba)
 First accepted: 185min (wakaba)
 Number of submissions: 12
 Number of accepted:5


Download Report