ICPC 2007年国内予選問題D

問題はこちら:http://icpc.logos.ic.i.u-tokyo.ac.jp/icpc2007/contest/D_ja.html
崖登り。コンテスト中は問題見た瞬間にすぐ解ける問題とわかり
「ああ、書くだけだね」と完全に丸投げしてしまったけど、
終わってみると結構4問解けているチームが多い。
これ全員がダイクストラ(もしくはベルマンフォードあたり)書いたのかなあ。コンテストのレベル上がったなあとその時は思っていたけど、必ずしもそうでないことに気づきました。

この問題はもちろん最短路問題だけど、一般的な最短路問題より少し簡単で実は深さ優先探索でも解ける。その場合は例えば以下のようなアルゴリズムでよいのではないか。

グラフ的に行けるところへ距離を加算しながら再帰していって、ある(位置,足)にきたときの始点からの距離が前に到達した時より長かったら、それ以上探索する必要がないから枝狩り

ポイントは各ステップにおける距離(すべりやすさ)が高々9までということ。同じ点を2回通らずに別の点まで移動した場合、距離の上限はW*H*2*9となる。

よって、距離の更新が行われる回数は各点についてW*H*2*9回で抑えられるため、最終的に計算量は
(W*H*2)*(W*H*2*9)*9で、最大でも10億くらい。国内予選なら間に合う時間なんじゃないかな。

振り返ってみれば、結局ダイクストラを使わないと解けない問題は、知る限り国内予選では一度も出ていないわけで、「特別知識がなくても解ける」日本の問題のクオリティは高いなあと改めて思ったり。