コンテンツにスキップ

ABC481 F - Evil Shortest Path

サイト
AtCoder
コンテスト
ABC481
問題
F - Evil Shortest Path
難易度
1621

NN 頂点 MM 辺の有向グラフがあり、各辺には 11 以上 99 以下の数字が書かれています。通った辺の数字を順につなげた整数をその移動のスコアとします。v=2,3,…,Nv = 2, 3, \ldots, N のそれぞれについて、頂点 11 から頂点 vv へ移動するときのスコアの最小値を 998244353998244353 で割ったあまりを求める問題です。

同じ頂点や辺を何度通ってもよく、頂点 11 から全頂点に到達できることが保証されます(2≤N≤2×1052 \le N \le 2 \times 10^5、N−1≤M≤2×105N - 1 \le M \le 2 \times 10^5)。

辺の数字はどれも 11 以上なので、スコアの桁数は通った辺の本数に等しく、桁数が少ないほどスコアは小さくなります。よって、スコアが最小になる移動は、頂点 11 からの最短路(辺の本数が最小の移動)のどれかです。桁数が同じ整数どうしの大小は、数字の列の辞書順と一致するので、最短路のうち数字の列が辞書順で最小のものを求めればよいです。

頂点 11 からの最短距離 dd を BFS で求めます。最短路で使える辺は、dv=du+1d_v = d_u + 1 を満たす辺 u→vu \to v だけです。頂点 vv への辞書順最小の列を svs_v とすると、

sv=min⁡u→v, dv=du+1(su の後ろに辺の数字をつなげた列)s_v = \min_{u \to v,\ d_v = d_u + 1} (s_u \text{ の後ろに辺の数字をつなげた列})

です。長さの同じ列どうしでは、sus_u より大きい列の後ろに数字をつなげても、sus_u の後ろにつなげた列より小さくはならないからです。dd の小さい順に頂点を見ていけば、sus_u を使うときには sus_u が確定しています。

列 svs_v の長さは最大で N−1N - 1 になるので、すべての列をそのまま持つと間に合いません。そこで、列を Trie のノードで表します。sus_u のノードから辺の数字で 1 文字進んだノードが「sus_u の後ろに数字をつなげた列」です。1 本の辺でノードは高々 1 個しか増えないので、ノードは M+1M + 1 個以下です。

2 つのノードの列の辞書順の比較は、2 つのノードの最小共通祖先(LCA)のすぐ下の文字を比べればできます。ノードごとに祖先への飛び先を持っておけば、LCA は O(log⁡N)O(\log N) で求まります。

答えのあまりは、svs_v を更新するたびに (su のあまり)×10+(数字)(s_u \text{ のあまり}) \times 10 + (\text{数字}) として一緒に更新します。計算量は O((N+M)log⁡N)O((N + M) \log N) です。

なお、Trie を使わなくても、同じ距離の頂点どうしの svs_v の順位を距離ごとに求めておき、「sus_u の順位、辺の数字」の組をソートして次の距離の順位を決める方法でも解けます。

別解:スコアを距離にしてダイクストラ法

Section titled “別解:スコアを距離にしてダイクストラ法”

スコアを「数字の列の長さで比べ、長さが同じなら辞書順で比べる」値と考えると、この問題はスコアを距離とする最短路問題です。この距離には次の 2 つの性質があります。

  • 辺をたどると、列が 1 文字長くなるので、距離は必ず大きくなる。
  • 列 aa が列 bb より小さければ、同じ数字をつなげた後も、aa のほうが bb 以下になる。

この 2 つが成り立つので、ダイクストラ法がそのまま使えます。距離は上と同じく Trie のノードで持ち、比較 1 回が O(log⁡N)O(\log N) なので、全体の計算量は O(Mlog⁡Mlog⁡N)O(M \log M \log N) です。BFS の層ごとに処理する工夫を、ダイクストラ法に任せる形になります。

C++(BFS)
#include "shogo-library/base/all"
#include "shogo-library/graph/shortest-path.hpp"
#include "shogo-library/math/modint.hpp"
#include "shogo-library/string/trie.hpp"
#include "shogo-library/utility/vector_func.hpp"
using mint = modint998244353;
void solve() {
LL(N, M);
Graph<> g(N);
g.read(M, -1, true, true);
auto d = shortest_path(g, 0, false).dist;
Trie<9, 1> trie;
vl node(N, -1);
vec<mint> ans(N);
node[0] = 0;
for (ll u : sorted_idx(d)) {
for (auto &e : g[u]) {
if (d[e.dst] != d[u] + 1)
continue;
ll v = trie.extend(node[u], e.cost);
if (node[e.dst] == -1 || trie.less(v, node[e.dst])) {
node[e.dst] = v;
ans[e.dst] = ans[u] * 10 + e.cost;
}
}
}
rep(v, 1, N) print(ans[v]);
}
int main() {
std::cin.tie(nullptr);
std::ios_base::sync_with_stdio(false);
solve();
}

g.read(M, -1, true, true) は、辺の数字を重みとして、有向辺を MM 本読みます。shortest_path(g, 0, false) の第 3 引数 false は重みを無視することを表し、BFS で辺の本数の最短距離を求めます。

Trie<9, 1> は、文字 11 から 99 を使う Trie です。根(ノード 00)が空の列で、頂点 11 の列に対応します。node[v] は svs_v のノード、ans[v] はそのあまりです。

sorted_idx(d) は d の小さい順に並べた頂点の番号の列です。trie.extend(node[u], e.cost) で sus_u の後ろに辺の数字をつなげた列のノードを(なければ作って)求め、trie.less(v, node[e.dst]) で、いまの svs_v より辞書順で小さいかを O(log⁡N)O(\log N) で比べています。

使用ライブラリ:cpp_include@4b58304

C++(ダイクストラ法)
#include "shogo-library/base/all"
#include "shogo-library/graph/shortest-path.hpp"
#include "shogo-library/math/modint.hpp"
#include "shogo-library/string/trie.hpp"
using mint = modint998244353;
Trie<9, 1> trie;
struct Score {
ll node = 0;
ll digit = 0;
mint val = 0;
Score() = default;
Score(ll digit) : digit(digit) {}
static Score inf() {
Score res;
res.node = -1;
return res;
}
friend Score operator+(const Score &a, const Score &e) {
Score res;
res.node = trie.extend(a.node, e.digit);
res.val = a.val * 10 + e.digit;
return res;
}
friend bool operator<(const Score &a, const Score &b) {
if (a.node == -1)
return false;
if (b.node == -1)
return true;
if (trie.depth(a.node) != trie.depth(b.node))
return trie.depth(a.node) < trie.depth(b.node);
return trie.less(a.node, b.node);
}
friend bool operator>(const Score &a, const Score &b) { return b < a; }
friend bool operator==(const Score &a, const Score &b) { return a.node == b.node; }
friend std::istream &operator>>(std::istream &is, Score &s) { return is >> s.digit; }
};
void solve() {
LL(N, M);
Graph<Score> g(N);
g.read(M, -1, true, true);
auto d = shortest_path(g, 0, true, Score::inf()).dist;
rep(v, 1, N) print(d[v].val);
}
int main() {
std::cin.tie(nullptr);
std::ios_base::sync_with_stdio(false);
solve();
}

Score は距離と辺のコストの両方に使う型です。距離としては、node がスコアの列の Trie のノード、val がそのあまりです。辺のコストとしては、digit に辺の数字を入れます。

  • operator+ は、距離に辺のコストを足す操作で、Trie を辺の数字で 1 文字進めます。
  • operator< は、列の長さ(Trie の深さ)で比べ、同じなら trie.less で辞書順に比べます。node == -1 は到達できないことを表す最大の値 inf() です。
  • operator> と operator== は、ライブラリのダイクストラ法の中で、距離の比較と未到達の判定(inf との比較)に使われます。
  • shortest_path の inf の既定値は std::numeric_limits<Cost>::max() / 4 で、この型では使えないので、Score::inf() を渡しています。
  • g.read は、重みを Cost c(1) で作ってから std::cin >> c で読むので、整数からのコンストラクタと operator>> を用意しています。始点の距離 0 は Score(0) で、Trie の根(空の列)になります。

使用ライブラリ:cpp_include@4b58304