diverta 2019 Programming Contest 2 D - Squirrel Merchant (600)

解法：解説解。

取引所Aでドングリ⇒金属、取引所Bで金属⇒ドングリの交換をそれぞれ行うことを考える。例えば金を用いた場合は、ドングリgA個を用いてドングリgBを手に入れることができる。

実はこれはナップサックの枠組みで考えることができる。つまり、交換に使用するドングリ(gA)を重さ、交換によって追加的に得られるドングリ（gB - gA）を価値とする、個数制限なしナップサックと見なすことができる。また、全く交換していない状態でも価値がNあることに注意する。

取引所Bでドングリ⇒金属、取引所Aで金属⇒ドングリを行う場合も同様に行えばよい。交換によりドングリの個数が減ることもありうるが、それを気にせずナップサックを行うことができる。

mini notes