ARC128_A – Gold and Silver
問題
提出
解けたが、もっと簡単な方法があった
提出した解法は、dpして結果から逆算して取引したかしてないかを算出した。
dp配列に格納する値は以下のようにした。
$dp[i][j] : i番目まで見た時の金の量(j=0)と銀の量(j=1)$
これで提出すると金の量、銀の量はlong doubleでは精度が足りずTLEした。
boostの多倍長浮動小数点型を使いACした。
公式解説を見ると、dpする必要はなかった。
$x_i$日目に金から銀に交換し、$y_i$日目に金に交換するとき、最適な交換の仕方は、 $x_1<y_1<…<x_i<y_i…<x_k<y_k$を用いて、以下のようになる。
$x_1$で金から銀に交換して、$y_1$で銀から銀に交換する。
$x_2$で金から銀に交換して、$y_2$で銀から銀に交換する。
$x_k$で金から銀に交換して、$y_k$で銀から銀に交換する。
$x_1$日目に金から銀に交換して、$y_1$日目に銀から金に交換すると、金の量は$\frac{A_{x_1}}{A_{y_1}}$倍になる。
ここで、$x_1$日目から$y_1$日目までに$t_1…t_m$日あるとする。
この間金と銀の交換を繰り返すとする。
すると、$x_1$日目から$t_1$日目の交換で$\frac{A_{x_1}}{A_{t_1}}$になる。
$t_1$日目から$t_2$日目の交換で$\frac{A_{x_1}}{A_{t_1}}\frac{A_{t_1}}{A_{t_2}} =\frac{A_{x_1}}{A_{t_2}} $になる。
$t_2$日目から$t_3$日目の交換で$\frac{A_{x_1}}{A_{t_2}}\frac{A_{t_2}}{A_{t_3}} =\frac{A_{x_1}}{A_{t_3}} $になる。
$t_m$日目から$y_1$日目の交換で$\frac{A_{x_1}}{A_{t_m}}*\frac{A_{t_m}}{A_{y_1}} =\frac{A_{x_1}}{A_{y_1}} $になる。
つまり、毎日交換を繰り返しても最終的な答えは同じになる。
そこで、毎日交換を繰り返して金の量を最大にする方法を考える。
そうすると、$A_i>A_{i+1}$の時に交換するのが最適になる。
コメント