コンテンツにスキップ

辞書順

タグ「辞書順」の記事 2 件

ABC481 F - Evil Shortest Path

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

ShareOJ - Smallest and Largest Subarray

長さ NN の隠された整数列 AA について、連続部分列のうち辞書順で最小のものと最大のものを 1 つずつ答えるインタラクティブ問題です。

? l r l' r' と質問すると、(Al,…,Ar)(A_l, \dots, A_r) が (Al′,…,Ar′)(A_{l'}, \dots, A_{r'}) より辞書順で真に小さいかどうかが返ってきます。N=1000N = 1000 で、質問は Q=1500Q = 1500 回までです。

連続部分列 (Ai,…,Aj)(A_i, \dots, A_j) について、次のことがいえます。

  • 先頭の 1 要素 (Ai)(A_i) はこの列の接頭辞なので、(Ai)(A_i) 以下です。したがって、最小のものは長さ 1 の列 (Ai)(A_i) にとれます。
  • この列は接尾辞 (Ai,…,AN)(A_i, \dots, A_N) の接頭辞なので、接尾辞以下です。したがって、最大のものは接尾辞にとれます。

そこで、接尾辞どうしを比べることにします。長さの違う接尾辞が等しくなることはないので、NN 個の接尾辞はすべて大小が決まります。

  • 最大の接尾辞 (Ar,…,AN)(A_r, \dots, A_N) が、そのまま最大の連続部分列です。
  • 最小の接尾辞 (Al,…,AN)(A_l, \dots, A_N) の先頭 AlA_l は、AA の最小値です。先頭の値がより小さい接尾辞があれば、そちらのほうが小さいからです。よって (Al)(A_l) が最小の連続部分列です。

あとは、NN 個の接尾辞の最小と最大を、比較 15001500 回以内で求めればよいです。

最小と最大を別々に求めると 2(N−1)=19982(N - 1) = 1998 回かかり、間に合いません。

そこで、接尾辞を 2 つずつ組にします。まず組の中で比べ、小さいほうだけを今の最小の候補と、大きいほうだけを今の最大の候補と比べます。1 組あたりの比較は 3 回です。

最初の組は比べるだけで最小と最大の候補になるので 1 回です。N=1000N = 1000 は偶数なので組はちょうど 500500 個できて、比較は全部で 1+3×499=14981 + 3 \times 499 = 1498 回です。15001500 回に収まります。

これは C++ の std::minmax_element と同じ方法です。

Python
N, Q = map(int, input().split())
print("?", 1, N, 2, N, flush=True)
x = int(input())
if x:
l = 1
r = 2
else:
l = 2
r = 1
for i in range(1, N // 2):
print("?", 2 * i + 1, N, 2 * i + 2, N, flush=True)
x = int(input())
if x:
a = 2 * i + 1
b = 2 * i + 2
else:
a = 2 * i + 2
b = 2 * i + 1
print("?", a, N, l, N, flush=True)
x = int(input())
if x:
l = a
print("?", r, N, b, N, flush=True)
x = int(input())
if x:
r = b
print("!", l, l, r, N)

接尾辞 (Ai,…,AN)(A_i, \dots, A_N) を i N で表しています。l は最小の接尾辞の、r は最大の接尾辞の開始位置の候補です。各組では、小さいほうを a、大きいほうを b としています。