[AtCoder] M-SOLUTIONS プロコンオープン 2020 D – Road to Millionaire

問題

方針

貪欲法

\( i \) 日目に株を買えるだけ買うか、全て売るかどうかを考えます。\( i \) 日目の現金を \( m_i \) とします。

\( A_i < A_{i+1} \) のとき

このとき、\( 1 \) 株当たり \( A_{i+1} – A_i\) 円の利益が出るので、株を買えるだけ買います。

\( A_i \geq A_{i+1} \) のとき

このとき、全て株を売ります。ここで、\(A_{i} < A_{i+2} \) のときを考えます。

\( i \) 日目に株を \( k \) 株を持ち売買しないとすると、\( i +1 \) 日目に \( m_i \) 円で \( A_{i+1} \)円の株を買えるだけ買い、\( i + 2 \) 日目に株を全て売ると、

\[ A_{i+2} \times \left ( k + \dfrac{m_{i}}{A_{i+1}} \right )\]

円の利益となります。一方で \( i \) 日目に株を全て売り、\( i + 1 \) 日目に買える株数は、

\[ \dfrac{kA_{i} + m_i}{A_{i+1}}\]

となり、現金は便宜上 \( 0 \) 円となります。そして、\( i + 2 \) 日目に全て株を売ると、

\[ A_{i+2} \times \left ( k \dfrac{A_i}{A_{i+1}}+ \dfrac{m_{i}}{A_{i+1}} \right )\]

となります。

\[ \dfrac{A_i}{A_{i+1}} \geq 1\]

なので、\( i \) 日目に全て株を売った方が利益が大きいことが分かります。

コード