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

2020年7月26日2020年12月14日

問題

方針

貪欲法

\( 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 \) 日目に全て株を売った方が利益が大きいことが分かります。

コード

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main() {
    int N;
    cin >> N;
    ll A[N];
    for (int i = 0; i < N; i++) {
        cin >> A[i];
    }
    ll m = 1000;
    ll k = 0;
    for (int i = 0; i < N - 1; i++) {
        if (A[i] < A[i + 1] && m != 0) {
            k += m / A[i];
            m = m - (m / A[i]) * A[i];
        } else if (A[i] >= A[i + 1]) {
            m += A[i] * k;
            k = 0;
        }
    }
    cout << m + A[N - 1] * k << "\n";
    return 0;
}