diverta 2019 Programming Contest 2 - D Squirrel Merchant

• 問題
• AC

やることは次の２つのステップにわかれている:

1. 取引所Aでどんぐりを金属に交換し、取引所Bで金属をどんぐりに交換する
2. 取引所Bでどんぐりを金属に交換し、取引所Aで金属をどんぐりに交換する

それぞれのステップでどんぐりを最大化すればよい。

また、$g_A \le g_B$なら金を交換するのはステップ1のみでよいし、$g_A \ge g_B$ならステップ2のみでよい。銀、銅についても同様である。つまり、交換レートの大小関係に応じて、次の3つの場合を考えればよい。

$g_A \le g_B$, $s_A \le s_B$, $b_A \le b_B$の場合

ステップ1で金銀銅を交換し、ステップ2では何もしないのが最適である。

Aで金を$x$グラム、銀を$y$グラム買うとすると、銅は最大で$\lfloor (N - xg_A - ys_A)/b_A \rfloor$買えるので、最終的などんぐりの数が決まる。$xg_A + ys_A \le N$という条件下で最大値を全探索すればよい。${\mathcal O}(N^2)$。

$g_A \le g_B$, $s_A \le s_B$, $b_A \ge b_B$の場合

ステップ1で金銀を交換し、ステップ2で銅を交換するのが最適である、

ステップ1で金を$x$グラム買うとすると、銀は最大で$\lfloor (N - xg_A )/s_A \rfloor$グラム買えるので、ステップ1終了後のどんぐりの数が決まる。$xg_A \le N$という条件下で最大値を全探索すればよい。

ステップ1終了後のどんぐりの数の最大値を$M$とする。ステップ2ではできるだけ多くの銅を交換するのがよいため、最終的な最大値は$\lfloor M/b_B \rfloor \cdot b_A + M\%b_B$である。（ただし、$\%$はあまりを求める演算子とする。）計算量は${\mathcal O}(N)$。

$g_A \le g_B$, $s_A \ge s_B$, $b_A \ge b_B$の場合

ステップ1で金を交換し、ステップ2で銀銅を交換するのが最適である、

ステップ1ではできるだけ多くの金を交換するのがよく、どんぐりの数の最大値は$M := \lfloor N/g_A \rfloor \cdot g_B + N\%g_A$である。

ステップ2で銀を$x$グラム買うとすると、銅は最大で$\lfloor (M - xs_B )/b_B \rfloor$グラム買えるので、最終的などんぐりの数が決まる。$xs_B \le M$という条件下で最大値を全探索すればよい。計算量は${\mathcal O}(M) = {\mathcal O}(Ng_B)$。□

ほかのパターンは適当に定数を入れ替えれば上のどれかに帰着する。$c := \max(g_A, g_B, s_A, s_B, b_A, b_B)$とすると、全体の計算量は${\mathcal O}(N\max(N, c))$である。

---

この方針は金属が3種類しかないことに依存していて、4種類だと早くも破綻してしまう。¹

３種類なら場合分けが通用するだろうというあたりから考察を始めるので、想定解のDPは一瞬も考えなかった。それはそれでいいとしても、たとえば$k$種類だったらDPを書けただろうか？ さすがに書けると思いたいけど、あまり自信はない。

---

1. 深く考えてないけど、2-2, 3-1の買い方は上と同じ方針で良さそう。0-4, 4-0の買い方は半分全列挙で何とかなる？ でも、1-3が間に合わない気がする。 ↩︎