くろたんく雑記帳

日常とか、わんちゃんとか、機械学習とか、競プロとか、

MENU

Python3で解く M-SOLUTIONS プロコンオープン 2020 D - Road to Millionaire

当たり前だが、安い時に買って、高い時に売ればいいっていうのを実装する。条件的にはその時点で所持する金と株の範囲内で1日に何回でも売り買いができるので、翌日上がる時に買えるだけ買って、翌日上がらないなら全部売るを常に繰り返せばいい。
こんな能力あったらいいなぁ・・・

概要

問題

  1. {\displaystyle n}日分の未来の株価がわかる。
  2. {\displaystyle i}日目の株価は{\displaystyle A_i}
  3. 最初の所持金は{\displaystyle 1000}円。
  4. 最終日に所持金を最大にする様に条件の範囲で売買を行なった場合の所持金はいくらになるか?

解くときに考えた内容

  • 最初は、最小値で買って、最大値で売ればいいのでは?と思ったが、そんなわけはない(サンプルの1つ目が)まさにその例外。
  • 要は、こんな感じ(図の0, 1は翌日下がるか上がるか)

    f:id:black_tank_top:20200726100420j:plain
    翌日上がるか上がらないかで、買う、売るを決めるイメージ
    最初の翌日上がる時に買えるだけ買って、上がらないと分かれば売るを繰り返す。

  • 戦略は以下

    1. 翌日上がるか上がらないかのリストを作る。
    2. 翌日上がる日に所持金で買えるだけ買う。
    3. 翌日下がる日に売れるだけ売る。
    4. 最終日に株を持ってたら売る。
  • これをそのまま実装すればいい。
    • 買えるだけ買ってしまうので翌日上がるが続いてもその日は買えない。
      (その手前(より株価が低い時)に買いきっている状態になるので問題ない)

コード

n = int(input())
A = [int(x) for x in input().split()]
# 最初の所持金
money = 1000
# 所有株数
kabu_c = 0
# 予言で翌日上がるかどうかのリスト
l = list()
for i in range(n-1):
    if A[i+1] - A[i] > 0:
        l.append(1)
    else:
        l.append(0)
for idx, i in enumerate(l):
    # 翌日上がってかつその時の株価で買える所持金があるなら買う。
    if i == 1 and money - A[idx] >= 0:
        kabu_c = money // A[idx]
        money = money - (kabu_c * A[idx])
    # 翌日上がらないなら売っちゃう(その時点での利幅ゲット)
    if i == 0:
        money = money + (kabu_c * A[idx])
        kabu_c = 0
# 上がり調子だと最終日で売り切ってない可能性があるので所持している株は最終日で売り切る
if kabu_c > 0:
    money = money + (kabu_c * A[n-1])
print(money)