はむこの勉強記録

http://bit.ly/2ktf20t の写し

素直なDPが普通に解けるようになってきた

概要

5次元だろうが、素直なDPならば結構思いつくようになったし、バグって無限時間溶かすことがなくなってきました。僕は青コーダーなんで、ほんまあまり役に立たない記事ですが、ある種の「アルゴリズム設計者の発達過程」として見てもらえれば良いです。

できるようになったこと

  • あまりDPをバグらせない。バグっても直せる。
  • そもそも「こんなんDPじゃなきゃ無理w」という感覚がついた(これは結構前に)。凸凹感覚というか、全探索しないといけなそうだけど2nとかn!とかで、他に解放が思いつかない場合など。隣と関係なさそう感(一番近い回文数列みたいなやつはきついよなあ)みたいなのもわかる

できなかった時との比較

  • 少し考察を眺めに取るようにした。厳密に考えるようになった。紙にきちんと数式に書くようになった。(これはDPの状態と遷移をコードに明示することともつながっていそう)
  • デバッグ時、自分の目で経路復元をするようになった(つまり経路復元ができるようになることは普通のDPのデバッグに必須。どこから来た値なのかを探す必要がしばしばあるので)
  • バグっていようがいまいが、とりまデバッグ出力を書くようになった(必ずバグってるので)。有効な状態(INFとか0とか自明じゃないもの)について、I << j <<< “ : “ << val << “ “ << hoge << “ “ << hugaみたいなデバッグ出力ををするようになった。遷移後の値を出力するようにした。
  • コメントに必ず状態と遷移を書くようにした
  • 配っているのか集めているのかは必ずコメントで明記するようにした。
  • 何でも一般化してみるようになった。長さnのpermutationの中で、転倒数がkのものは?とか言われたら、長さiのpermutationのなかで、転倒数がjのものは?と言い換えてみる

個人的に効いたと思った問題

  • Aho上のDPを3問解いた。
  • 経路復元の問題を2問解いた(これがないとデバッグができないと思う)
  • 何個かDPの図を含むEditorialを書いた。どこが自由度があり、どこが固定的なのかを意識するのに結構役立った気がする。

Codeforces #432 Div2 D. Arpa and a list of numbers

docs.google.com

Codeforces #430 Div2 D - Vitya and Strange Lesson

docs.google.com

Codeforces #429 Div2 D. Leha and another game about graph

docs.google.com

Codeforces #429 Div2 D. Leha and another game about graph (TLE)

docs.google.com