昨日解いた競プロの問題の解説/感想などを書いていきます
書いてる人について
atcoderで競技プログラミングをやっています。一年半くらいのキャリアです。青タッチも経験しましたが、現在は水コーダーです。
解いた問題
最近は背伸びして黄diff精進をやってます。
注意
以下この問題のネタバレを含みます。
典型
- 計算量悪いdpを考えて高速化
- 実験エスパー
問題概要
株価の配列が与えらえる。一日にたかだか単位株しか売買できないという制約のもとで 売買を最適に指定したときの利益の最大値を求める。O(n^2)ではだめ。
考えたこと
- ソートして順に処理する
例えば一番高い時には、それより安い時がその前に一瞬でもあれば売るのが最適になる。こういうのをrange queryとして処理できないかを考えた。でも無理そう。 - 計算量悪いdpを考える
dp[i][j] = (i日目にj株持ってる時の損益の最大値)
とすれば遷移は、
dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - 1] - p[i], dp[i - 1][j + 1] + p[i])
みたいになり、O(n^2)で解くことができる。これを高速化しようとしたけど無理。ここでgive up。
解法
考えたことの2が結構惜しくて、実はこの遷移を単純化することができる。
階差数列に注目すると、(←どうやって思いつくん笑)実は単調増加列になっており、毎回p[i]を二つinsertしたあと最少の要素を消すような遷移になっている。これはmultisetで実現できる。
学んだこと
こんなのどうやって思いつくのかわからないが、少なくとも階差数列に注目することさえ何とか思いつけば、実験エスパーは可能と思われる。めんどくさがらず実験エスパーをしよう。また、階差数列をとるみたいなのはダメもとで試してみるのが大事なのかな...
感想
未来予知できるなら一日に複数株売買してもよくない？
提出コード
マクロ部分が多くて申し訳ない...
最後に
記事を書くの初めてなので、何か意見や要望があればお知らせください。
ではでは