DP まとめコンテスト A,B,Cをやって思ったこと
今回はDP(動的計画法)についてです。この前Educational DP Contest(略してEDPC)があったのですが、無事3完しかできなかったので、勉強の意味も兼ねて自分の目線からDPについて書いていきたいと思います。
すごい放棄してる部分はあるのですが、基本的な細かい説明の方はけんちょん氏の
qiita.com
を読めば大体わかります。
この記事では、DP初心者の自分の目線から見たDPの疑問点を挙げていきたいと思います。基本的に書きなぐり的なのになります。すいません。
A - Frog 1
配列の左から「移動するコストの最小値」で埋めていったらできた。嬉しかった。
B - Frog 2
できなかった。悔しい。原因は、初期化の時の大きい値を1 << 10で（十進数で10000000000だと思って）してしまったところだった。シフトは二進数の話だった。
C - Vacation
こんな風に、1日目のA~Cをセットしておいて、2日目、3日目と埋めていく。図のように、4日目にCプランを選んだ時の最大値は「3日目にAかBを選んだ時の最大値のうち大きい方に4日目のCプランの幸福度を足したもの」という感じで求められた。Cまでは自分の知識でDPの配列の埋め方が想像できたので良かった。
という感じです。Cまでは、イメージできる。Cまでは。
一旦分かっているCまででこの記事は区切っておきます。
思ったこと(箇条書き)
- 個人的なDPのイメージは「100マス計算」的なマス目を左上から順にZの字を書くように埋めていくイメージを持っている
- DP、vectorより ll [110][1010] みたいな方がいいのかな
- DPの配列みたいなの、グローバル変数にしてた方が切り替えが楽そう
- 文法的な方の実装力がついていかない
- forループを回す時、どこまで行けるか分からずにコアダンプor最後に到達しない現象が起こる
テクニック的な
- INFはdefineしたほうが楽(10000000007とか1LL << 60とかで)
- DPの配列、一番初めを0にすると問題文の方はたいてい1からなので、入力側を1ずらすテクニック
- vector
v(n, 初期値) で初期化できるらしい - 英語に自信がない人は、forループ回す時の変数の名前を無理にdpとかwとかvとかにせずに、omosaとかkachiにするとぱっと見で意味が分かるので、そのぶん自分がどこを間違えたのかなどが楽に確認できるので楽だと思う（たぶん）。
- if文、1文だけなら中括弧省略できるけど省略しないほうがいい、「ここどうなってるのかな…？」ってなった時にすぐにcoutを入れられるから。
- 紙に描くのは大切
