yukicoder contest 395

　ABの二完。

コンテストへのリンク

No.2366 登校

　解説AC。

　ダイクストラを使いそうなのは分かるので、どういうダイクストラを使ってどうすれば計算量を減らせるか考える問題。

　疲労度の最小値を求める問題なので、

・DP[座標][時間]=疲労度の最小値

　とするのは自然。ただ、これだと時間をどの範囲で取ればいいか分からないのだけれど、どの地点からもN+M-2歩以内で行けることから時間を絞れる、という考察が必要でした。

　こう書くと自然な考察で解けるので、解きたかったね……。

　そして、解説を読み直しながらこの文章を書いていたら、実装ミスしていたことに気付いたので、再提出＆自分のコードにChallengeにしておいた。

　時間を巻き戻すとき、昔過ぎる時間に巻き戻る遷移を禁じた実装をしていました。