M-SOLUTIONS プロコンオープン 2020 D. Road to Millionaire

問題

N日間の株価の1株あたりの金額A_i円がわかっている。
最初、1000円の所持金から、毎日株の売買(所持金や持っている株数までで)が可能な時、最終日の所持金を最大化せよ。

制約

• 2 <= N <= 80
• 100 <= A_i <= 200

解法1

No.664 超能力者Aと株価予測 - yukicoder
を思い出した。。。

売るときと買うときは、全部売ったり全部買ったりするのが最適。

(以下、正しいかわからないけど、自分の理解のメモ)
(X株,Y円)のときにx株だけ売ることを考えると、A_iでz株だけ売って、A_jで(x-z)株を売るので、(X-x株, Y+z*A_i+(x-z)*A_j円)になる。
A_i > A_jの場合は、z=xの場合が所持金最大になり、A_i <= A_jの場合は、z=0の場合が所持金最大になる。
なので、売るときは全部売るのが最適。
X-x株だけ残した場合でも、最終日に株を残す意味はなく、どこかで売ることになるが、A_kとA_lのときに売る場合でも同様に議論できて、結局どこかでまとめて売るのが最適になる。

また、買う時は、売るときに全部売っているはずなので、0株の時を考える。
(0株,Y円)で、所持金を少し残して、X株買えるうちx株だけ買うことを考えると、A_iでz株だけ買って、A_jの時x-z株を買うので、(x株, Y - (z*A_i + (x-z)*A_j)円)になる。
上記と同様に、zはz=0かz=Xの場合が最適になるので、どこかで全力買いすればよい。
また、上記と同様に、売るときは全部売るので、X株中一部だけ売買するのではなく、全部株をどこかで買ったほうがよくなるので、全部売る、全部買う、だけを考えれば良い。

dp[i][j] := i日目で、株数がjのときの所持金の最大値
を考える。
遷移は、何もしない、全部売る、できるだけ買う、の3通りになる。

ここで、株数jがどの程度まであり得るか考える。
jは、100で買って200で売る、というのを繰り返した場合、1000円から10->20->40->80->...と2日で2倍にしていけてしまう。
したがって、株数は10 * 2^40ぐらいまでありえてしまう。

一方、遷移をもっと詳細に考えてみると、株数が0の時は、所持金があるはずで、それを全力買いするか、何もしない、の2通りが考えられる。
株数が0でない場合は、制約より所持金の残りで1株だけ追加購入する、何もしない、全部売る(株数が0になる)、の3通りになる。
ただ、1株だけ追加購入するというのは、全部売ってからその株を全部買う場合とおなじになるので、考えなくて良い。

したがって、あり得る株数は、0と、0から所持金で買える最大株数、過去の最大株数で何もしない場合の株数、程度しかなく、状態数はかなり少ない。

よって、unordered_map< ll, ll > dp[85]とかで処理してあげれば十分高速に解ける。

解法2

dp[x] := x日目での所持金の最大値
とすると、i日に買ってj日に売る、ということを考えれば良いので、O(N^2)。