Codeforces 374div2

Codeforces Round #374 (Div. 2) - Codeforces
反省文のみ。
　かなりキツイ結果になった。
　A, Bは例のごとくやるだけ。落ちないと信じたいが。
　Cは頂点数<=5000、辺数<=5000の閉路なし有向グラフで１からNまで行くとき時間T以内に回れる最大の頂点数を答えろ、という問題。
　明らか典型っぽいのに詰めきれず、mapと拡張ダイクストラ法の嘘解法で無理矢理pretestを通した。
　TLEもMLEもギリギリだったので、たぶんsystestは落ちるだろう。
　この解法の何がダメかというと「閉路がない」条件を使えていないこと。
　上位の人の解法を見て気づいたのだが、結局このグラフはDAG（有向非巡回グラフ）だから、幅優先的にやっていくと訪問順がバシっと定まる（もちろん一意に決まるわけではなく、こっちの都合がいいように決める）（なんかあってるか不安だけど）。
　この順番を使うことで
dp[i][j] := i番目の頂点にいてj個まわってきた
　を効率よく埋めることができるというわけ。

　実装は明日に回してもう寝るけど、反省だなあ。
　DPやグラフはけっこう好んで練習してきたのに、僕は結局DPやグラフのことをなんにもわかっていなかった。
　悲しい。

[追記]
http://d.hatena.ne.jp/tanakh/20050703
　僕と似た症状にを経験された方のブログを発見した。
　そういえば、初めて拡張ダイクストラ法を実装した「全探索おねえさん」を解いたとき、最初はメモ化再帰で解こうとしたことを思い出した。
　結局アレは閉路があるからダイクストラを使うのか。
　
　１対全頂点で最短路を求める場合を考える。
　このとき閉路がなければ、ゴールから逆向きに考え
dp[i] := iからゴールへの距離
とするとminをとるメモ化再帰で簡単に求まって、これを明示的にやったのがトポロジカルソートということか。
　ダイクストラ法は最短距離が確定した頂点から配るDPをするが、これは結局ヒープを使ってトポロジカルソートする操作で、トポロジカル順序が確定していたらその通りに辿るだけだから普通のDPで大丈夫、と。
　今回はこれを拡張グラフに対して適応すれば良かったわけだ。
　うーんわかったようなわからないような。
　もう少し考えてみる必要がありそうだ。