配るDPは、集めるものと違って全部のDP領域を走査する必要があるというのと、
配る先のメモリがあるかどうかわからないのは面倒なので、DPテーブルを大きめに確保しておくほうが良い。

編集距離くらい自分で編み出したい…。
DPに慣れるために配るDPで書いた。

f:id:intelhamko:20170301224401j:plain

TopCoder SRM 665 Div1 Easy LuckySum

docs.google.com 配る桁DP、苦手の塊。

f:id:intelhamko:20170228132859j:plain

Codeforces #398 Div2 C - Garland

DFSやDPなどは、部分問題のマージが本質。
このような問題の場合、求めたい状態と遷移をしっかりと言語化することが極めて重要。
DFSの場合には、頂点にデータが載っているので、頂点にどのような情報を載せるかを検討して、実装可能性を吟味すること。いい加減に実装を始めない。

ループを回しきらないバグ、やっかいすぎる。

これくらいの実装問題になってくると、もはや早解きのために雑に変数を定義するより、コメントをきちんと書いたりテスト駆動的にやったりするほうがパフォーマンスがでるなあ。

日本に帰ってきてから、意味わからないくらいレーティングが落ちている。
今日は実は昼寝をしてやって、あまりにスムーズにコーディングでびっくりした

ドイツでは昼で眠くなかったから強かったのかもしれない。