Pythonで解くAtCoder(M-SOLUTIONS プロコンオープン 2020:D)
こんにちは、クルトンです！
この記事では
AtCoderの「M-SOLUTIONS プロコンオープン 2020」のD問題をPythonを使って解説します。
問題のリンクを載せておきます。
方針の立て方
入力例1をグラフにしました。黄色のところで株を買い、水色のところで株を売っています。
このグラフをみると、「極小値で株を買い、極大値で株を売る」という方針が立つと思います。
このようにグラフを書いて考えてみるのも方法の一つだと思います。
ではどのようにすれば、この方針で実装できるでしょうか？
極大値や極小値は、前後の要素との大小によって決まります。
そこで、連続する要素に注目して調べてみると
A[i] < A[i+1]
となるときに、i日目で株を買ってi+1日目に株を売ると利益が出ることが分かります。
実際に、このように購入してみましょう。
すると上のグラフのように、株を売るところと買うところが打ち消し合うことで、極小値で株を買い、極大値で株を売っていることになることが分かります。
このことから、A[i] < A[i+1]を満たすi日目にできるだけ株を買ってi+1日目にできるだけ株を売れば良いことが分かります。
解法
今回は解説がとても分かりやすかったので、解法については解説を読んでいただければ良いと思います。
DPを用いた解法のサンプルコード
Pythonで書いた解答を載せておきます。
今回は
- 貪欲法を使ってO(N)で解く
- もし貪欲法が思いつかなければ、DPを使ってO(N^2)で解く
という問題でした。
ではまたお会いしましょう！さようなら～
