bouzuya.hatenablog.com

ぼうずやのにっき

第八回 アルゴリズム実技検定 (PAST) H - 最短経路を解いた

第八回 アルゴリズム実技検定 (PAST) H - 最短経路 を解いた。

問題: https://atcoder.jp/contests/past202109-open/tasks/past202109_h

N 頂点の重み付きの木において「最短距離が X になる相異なる頂点の組」が存在するかを求める。 N <= 3000 。

まずは全探索を考える。すべての頂点の組について最短距離を求められるか。ワーシャル・フロイド法だと O(V^3) で間に合わない。各頂点についてダイクストラ法はちょっと間に合わないか。ギリ間に合うかもしれない。

木であることを活かせる方法はないか考える。木における任意の 2 頂点 u, v の距離は頂点からの距離を dist 共通の祖先を lca とすると dist[u] + dist[v] - dist[lca] * 2 の形で O(1) で求められる。 lca の計算はダブリングで前処理 O(NlogN) とクエリ O(logN) 。これで O(N^2 log N) で間に合う。

実装を進める過程で思い出したことには、木における距離は DFS で O(N) で求められる。ひょっとしたら各頂点から DFS でも間に合ったかも……。 → 解説を見たらこの方法で O(N^2) が正解だった。

ちなみにダイクストラ法でも間に合った。 PAST 本番だったらペナルティも大してないのでとりあえず投げてみたかもしれない。

今日のコミット。