Rustコトハジメ

プログラミング言語Rustと競プロに関する情報をお届けします。

【Mujin Programming Challenge 2018 E - 迷路】動的なダイクストラ法

解法が面白いと思いました。

動的ダイクストラ法というのは私が勝手にそう呼ぼうとしているだけです。

問題

迷路がある。始点から終点にたどり着きたいが、動きには以下の制限がある。時間ごとに、

  1. とどまる
  2. d[t%K]の方向に動く(d[i] = 上下左右どれか)

の2通りしかない。

最速タイムを求めよ。

制約: N,M=103, K=105

方針

誤答1

dist[i][j][k] := mod Kでkの時にi,jにいる最速タイム

O(NMK)で死

誤答2

私が考えた方法

dist[i][j] := i,jにいる最速タイム

方向 -> [k]

を予め計算しておき、次の方向までの時間はO(1)かO(log K)あたりで計算。

あとはふつうの迷路問題?

と思ったが、DPでやるとoutermost loopの回数が見積もれない。(最悪NMくらいかも)

正答

dist[i][j] := i,jにいる最速タイム

は良い。最速タイム(仮)が求まったら、ここから動的に隣のマスに対して辺を作る。この辺をコスト最小順でpriority queueに入れていくとダイクストラ法で解ける。

もとからグラフが与えられるわけではなく、動的にグラフが作られていくので、動的なダイクストラ法と呼ぶことにした。

クラスカル法でもグラフが動的に作られていく問題があったような?

次の方向までの時間は、dを後ろから見ていって事前計算すればO(1)で計算出来る。