見出し画像

M-SOLUTIONS プロコンオープン 2020見直し　D - Road to Millionaire

なにがし

問題

n日間のある株の株価が与えられるので、売買を行い手持ちの資金1000円が最大になる場合の金額を返す問題。ちなみに売買に手数料はかからないと言う夢の様な世界。

作成した解答(Python:33ms)

n = int(input())
a = [int(i) for i in input().split()]
assets = 1000
for i in range(n - 1):
       if a[i] < a[i + 1]:
           assets = assets//a[i] * a[i + 1] + assets%a[i]
print(assets)

解説

資金を最大化するためには、安いときに買って高いときに売れば良い。例えば以下の数列が与えられたとすると

100, 130, 130, 150, 115, 115, 150

以下の様に2日を比較して、金額が上がっている場合には売買すれば良い

画像1


解説動画を見て作成した解答（CPP:8ms）

#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
using namespace std;
using ll = long long;
using vi = vector<int>;

int main() {
   int n;
   cin >> n;
   vi a(n+1);
   rep(i, n) cin >> a.at(i+1);
   vector<ll> dp(n+1);
   dp.at(0) = 1000;
   for (int k = 1; k <= n; k++) {
       dp.at(k) = 0;
       for (int i = 0; i < k-1; i++) {
           int m = 99999;
           for (int j = i+1; j < k; j++){
               m = min(m, a.at(j));
           }
           dp.at(k) = max(dp.at(k), dp.at(i)/m*a.at(k)+dp.at(i)%m);
       }
   }
   ll x = 0;
   rep(i, n+1) x = max(x, dp.at(i));
   cout << x << endl;
   return 0;
}

DP(Dynamic Programming)を利用して解答しているらしいけど、良くわからなかったから、以下の投稿を参照しようと思った。


この記事が気に入ったらサポートをしてみませんか？