yukicoder No. 1308 ジャンプビーコン　解説（tester 解）

問題概要
tester 解
まとめ

問題概要

問題ページを参照してください

この問題は Advent Calendar Contest 2020 の 5 日めの問題で、自分は tester をしました。 adventar.org

tester 解

まず、以下のような DP を考えます

DP[i][j]  := x_i まで訪問して今ビーコンが頂点 j にあるときのコストの最小値

このとき、DP の更新式は以下のようになります。

DP[i][j] = min_k( DP[i-1][k] + cost )
  cost := dist[x[i-1]][x[i]]  ( j == k のとき )
  cost := min( dist[x[i-1]][j], C + dist[k][j] ) + dist[j][x[i]]  ( j != k のとき )

これをそのまま実装すると ${O(N^{2} Q)}$ になるため、高速化する必要があります（ここまでは yukicoder の方の解説に書いてあることと同様）。

上の DP の遷移をよく見ると、以下の値がわかっていれば遷移が減ることがわかります。

D[i][j]  := x_i まで訪問して、今ビーコンがどこにあっても良くて自分が頂点 j にいるときのコストの最小値

実際の遷移は以下のようになります。

DP[i][j] = min( DP[i-1][j] + dist[x[i-1]][x[i]], D[i-1][j] + dist[j][x[i]] )

ここで、D[i][j] は以下のように求められます。

D[i][j]  = min( min_k( DP[i][k] ) + dist[x[i]][j] ), min_k( DP[i][k] + C + dist[k][j] ) )

まだ ${O(N^{2} Q)}$ のままなので意味がありません。

ここで D[i][j] に思いを馳せると、これは例えば以下のような問題と同等な最短路問題のような形をしていることがわかります。

あなたは N 頂点 M 辺のグラフで表される町にいます。

各頂点ではメダルが売られており、頂点 j で売られているメダルの値段は P_j です。
また、各辺には通行料が定められており、辺 j の通行料は C_j です。

各頂点 1, ... , N について、その頂点からスタートしていずれかの頂点でメダルを買う、という行動にかかる金額の最小値を求めてください。

この問題はどうやって解けばよいでしょうか。結論から言ってしまうと、これは全頂点を始点とする Dijkstra をすることで ${O(M \log M)}$ で求めることができます（超頂点を用意し、その頂点から各頂点 j に対し長さ P_j の辺を張る、というように考えてもよいです）。

よって、D[i][j] も全ての j に対し ${O(\log N)}$ で求めることができ、全体で ${O(NQ \log N)}$ で求めることができました。

なお、解説で触れられている「遠回りをしてビーコンを設置することはない」という事実を用いて、最短路を x[i] に近づく方向にのみ更新することで ${O(NQ)}$ にすることも可能です（想定解は ${O(NQ)}$ でかつそもそもの定数倍がそこそこ重いため、C++ 以外の言語では ${O(NQ \log N)}$ だと通すのは難しいと思います）（tester したときは ${N, Q \le 5{,}000}$ , TL: 2 sec だったため、C++ でも ${O(NQ \log N)}$ は通らなかった）。