きろく

特筆すべき記録のまとめ

「みんなのプロコン 2018」:C - 駆引取引

問題

atcoder.jp

解法

dp1(b, i) := 今残っている商品が b で,財宝を i 個売却した時に商品を買って取引を終了する場合,得られる最大のスコア

dp2(b, i) := 今残っている商品が b で,財宝を i 個売却した時に得られる最大のスコア

の2つの DP を考える.

dp2 では,この時点で商品を買って取引を終了する場合と,まだ財宝の売却を続けるの2つの選択肢がある.前者を選んだ場合,その時の dp2 の解は dp1 になり,後者を選んだ場合,買えなくする商品を全通り試したなかの最小値になる(相手は解を最小化しようとするから).

dp1 では,もし今持っている金額ですべての商品を買える場合はすべて買うのが最適.金額が足りない場合は,買うのをあきらめる商品を全探索する.

全体で O(2^N * N).

解答

atcoder.jp

dp1 の計算量が大きくなっていたため 1 TLE してしまった.2つの DP を組み合わせるテクだった.

f:id:babcs2035:20181220185422p:plain