diverta 2019 Programming Contest 2-D:Squirrel Merchant

方針立ってから時間かけ過ぎた...。

問題

解法

　まず1つの金属について考える。例えば $g_A \lt g_B$ なら、Aでどんぐりを金にして、Bで金をどんぐりにするという行為以外ありえない。このように不等号の向きを見れば、ある程度取るべき行動が確定する。金属の種類の違いを無視すれば、3つの不等号の向きの組み合わせは4通りなので、これで場合分けをし、全探索をすることを考えよう。 $g,s,b$ の3種類の金属をまとめて $m$ を書くことにする。

3種類すべて $m_A\leq m_B$ のとき、取引所Aで金を $i$ 個、銀を $j$ 個買うと決めると、銅を買う個数も勝手に決まる。よって、 $i,j$ について全探索して $O(N^2)$ となる。
3種類すべて $m_A\geq m_B$ のとき、1の場合と同様にすればよい。
$m_A \leq m_B$ となる金属が2種類のとき、取引所Aでその2種類の金属をいくつか買い、取引所Bでどんぐりにした後、 $m_A \geq m_B$ である金属を買えるだけ買い、取引所Aでその金属をすべてどんぐりにするという行動を考えればよい。したがって、最初に取引所Aで $m_A \leq m_B$ となる2種類の金属をそれぞれいくつ買うかを決めることで $O(N^2)$ の全探索が可能となる。
$m_A \leq m_B$ となる金属が1種類のとき、取引所Aでその金属を買えるだけ買い、取引所Bでその金属をどんぐりにしてから、 $m_A \geq m_B$ である2種類の金属をうまく買って、取引所Aですべてどんぐりにするという行動を考えればよい。全探索すべきは、取引所Bでの金属の買い方だが、これは片方を何個買うかを決めればよいので、取引所Bについた時点でのドングリの個数がネックになる。これは $O(N\max(ga,sa,ba))$ であり、全探索して間に合う。