きろく

特筆すべき記録のまとめ

diverta 2019 Programming Contest 2:D - Squirrel Merchant

問題

atcoder.jp

解法

取引所 A でいくつかのどんぐりを金属に変え,取引所 B で金属を全てどんぐりに変えていくつかのどんぐりを金属に変え,取引所 A で金属を全てどんぐりに変えるように行動すればよい.途中の取引所 B で金属を全てどんぐりに変えるのは,金属のまま持っていても最後の取引所 A で全てどんぐりに変えることになり,得をしないから.A -> B と B -> A の行動は初期のどんぐりの個数は違ってくるが,それぞれ独立に考えられる.ここで以下の DP を考える:

dp1(i) := どんぐりが i 個あるとき,A -> B で行う操作を行った後のどんぐりの個数の最大値

dp2(i) := どんぐりが i 個あるとき,B -> A で行う操作を行った後のどんぐりの個数の最大値

それぞれの遷移は

dp1(i) = max(dp1(i - ga) + gb, dp1(i - sa) + sb, dp1(i - ba) + bb, i)

dp2(i) = max(dp2(i - gb) + ga, dp2(i - sb) + sa, dp2(i - bb) + ba, i)

となる.実装をメモ化再帰で行うと 1 ケースだけ RE となってしまい通らないので,for DP でやること.O(N * 5000).

解答

atcoder.jp

f:id:babcs2035:20190622151442p:plain