ゆらのふなびと

競プロ, Python, C++

SRM232 Div2 Hard StockHistory

ちょくだいさんの本(↓)に載っていたので解いた。

蟻本よりTopCoder特化な感じ。「蟻本難しい!」「知識以前の考え方を身に着けたい!」という方はぜひ。

問題

https://community.topcoder.com/stat?c=problem_statement&pm=3971

以下の条件で投資を行ったとき、得られる最大の利益を答えよ。

  • あなたは最初の月にはinitialInvestmentドルまで、次の月からはmonthlyContributionドルまで投資することができる。

  • 毎月における各銘柄の値段stockPricesがわかっている。

  • 端株も購入できる(1.5株など)

なお、返り値は小数部分を四捨五入すること。

解法

サンプル3が最大のヒント。ある月において、もし投資を行うのであれば、その月の値段と最終月の値段を比べて利益率が最も高くなるような銘柄に全額投資するのが最適である。しかしその月以降にもっと利益率の高い買い方が存在するなら、お金はセーブしておいた方がよい。これを前から考えていくとしんどいので、サンプル3のように後ろから考える。そうすると以下のようにすればよい。

Mi = (月iから最後の月までの最大利益率) とすると、

  • Mi <= 1 である間は投資しない
  • Mi >= 1 であれば、Miが等しい区間の金額をその区間の最終月に投資する

下のコードにはコメントとデバッグ用のprintがついています。

class StockHistory:
    def maximumEarnings(self, initialInvestment, monthlyContribution, raw_stockPrices):
        stockPrices = []
        for i in range(len(raw_stockPrices)):
            stockPrices.append(list(map(int, raw_stockPrices[i].split())))

        num_month = len(stockPrices) - 1
        num_kind = len(stockPrices[0])

        # 一番最後の月から、初めて利益が出る月まで戻る
        # この間のお金は無駄になる
        m = num_month
        t_max_ratio = 1
        while m > 0:
            for k in range(num_kind):
                t = stockPrices[-1][k] / stockPrices[m - 1][k]
                if t > t_max_ratio:
                    t_max_ratio = t
            if t_max_ratio > 1:
                break
            m-= 1

        lim_month = m

        # どの月でも利益率が1以上にならないなら、利益は0
        if lim_month == 0:
            return 0

        max_ratio = t_max_ratio
        cur_money = 0
        total_profit = 0

        print(lim_month)

        # 未来の月から見て、最大利益率が変わったら初めてその最大利益率となった月で投資
        for m in range(lim_month)[::-1]:

            # 各種類を買ったときの利益率を計算し、最大のものを得る
            t_max_ratio = 1
            for k in range(num_kind):
                t = stockPrices[-1][k] / stockPrices[m][k]
                if t > t_max_ratio:
                    t_max_ratio = t

            # この月の最大利益が未来の月の最大利益を上回っていれば
            if t_max_ratio > max_ratio:
                total_profit += cur_money * (max_ratio - 1)
                print(total_profit, cur_money, max_ratio, t_max_ratio)
                cur_money = 0
                max_ratio = t_max_ratio

            if m != 0:
                cur_money += monthlyContribution
            else:
                cur_money += initialInvestment

        # 最初の月に戻ってきたときお金が余っていればここで足される
        total_profit += cur_money * (max_ratio - 1)
        print(total_profit, cur_money, max_ratio, t_max_ratio)

        return round(total_profit)


所要時間: 77'14

読解10分、考察10分、実装55分という感じ。本番で出会ったら間に合わないぞ…。

ちなみにちょくだいさんの本では「後ろから投資する月を記録(Miが変わったタイミング)→前から走査して総和を計算」としていてスマートだった。詳しくは本を買って。