AtCoder Beginner Contest 037 D : 経路

DPだと思うけど、きれいな（for文で書けるような）漸化式が思いつかない。

PriorityQueueを使えばトポロジカル順序ソートできるかな・・・？
→重複除去とか、dp[i][j]に値を入れる方法が分からない・・・。

メモ化再帰で解く。なーんだ。

きれいなDPが書けないと解けないって思ってしまうのよくない。
簡単なセットなのに解説を見てしまって悔しい。

やっぱりPriorityQueue使えば良さそう。
大きいほうから遷移していけばいいのでは？　→　AC

FastScannerを利用しないとTLEになってしまう。なんでだろ。
クラスのnewで結構時間かかっちゃうのかな。

でも、O(HW) -> O(HW log HW)になっちゃうな。

ただ単に dp[i][j] := (j, i)を出発点とする経路の総数
と、いう定義を思いつけなかっただけみたいだな。
「DPだと思う（どう定義できるか分かるとは言ってない）」
って感じで良くないな。

整理してFastScannerなしでACできた。

やったこと