再帰的な構造の迷路。考察が結構面白いので解法は読まない方がいい。
はじめに
2018年11月18日に開催された XIX Open Cup named afer E.V. Pankratiev, Grand Prix of Siberia の問11「Recursive Circuit」の問題と解法を述べる。
Open Cup
Open CupはICPCに似たルールで5時間 10~14問程度の3人以下チームのプログラミングコンテスト。参加が招待制なので、参加したい場合は参加者の誰かに尋ねて日本の管理者を紹介してもらってアカウントを作ってもらうことになる。問題を解きたいだけなら Codeforces (Gym - Codeforces) で一部が利用できる。問題文を読むだけならば List of All Open Cup Contests - Codeforces から閲覧できる。
XIX Open Cup, Grand Prix of Siberia
Open Cupはどこかの大学のプログラミングキャンプなどで出題された問題を再利用する形で出題されることが多いと思う。今回は Siberia。
この XIX Open Cup, Grand Prix of Siberia はGYMに移植されていないので Open Cup アカウントを持っていない人はジャッジが利用できない。問題文は XIX Open Cup. Stage 7. Grand Prix of Siberia.pdf — Яндекс.Диск で閲覧できる。
Recursive Circuit は XIX の中の Stage 7 の中の11問目。
問題
再帰的構造を持つ回路を考える。回路の内部には S 個のサブ回路が配置してある。サブ回路は回路全体と同じ構造をしている、つまり無限に再帰的な構造をした回路になっている（画像はもとの問題文より）。
回路は N 個の端子を持つ。
- 1 から K 番の端子は回路の外部から利用することができる。
- a*K + j 番の端子は a 番目のサブ回路の j 番目の外部端子である。
- 残りの端子はほかの端子を繋ぐための端子である。
いくつかの端子のペアは短絡に繋がっている。
最も外側の回路の外部端子2つを選んで片方からもう片方に信号を流すときに少なくともどれだけの「深さ」まで潜るかを求めたい。深さとは、最も外側の回路の深さが 0。内部の回路の深さは 1。そのさらに内部の回路の深さは 2 ...。
深さを求める Q 個の質問に答えよ。ただし信号が流れない場合は-1を出力せよ。
例えば、(3, 4) と質問された場合、上の画像の3番の端子と4番の端子に信号を流すにはサブ回路のサブ回路を通る必要があるので深さは2。
制約
K * (S+1) <= N <= 100000
M <= 100000
Q <= 100000
他の制約は原文を見る。
解法
↓
↓
↓
↓
↓
↓
↓
↓
↓
↓
↓
↓
↓
↓
↓
↓
↓
↓
↓
↓
与えられている辺を重み 0 として頂点を繋ぐ、ただしすでに連結な頂点同士ならば無視する。最も外側の回路において 2 つの外部端子が連結になった時、全てのサブ回路の対応する端子を重み 1 の辺で繋ぐことにする、つまり重み 1 の辺を S 本追加する。重み 0 の辺を全て見たら重み 1 の辺を同様に見ていく。
重み 1 の辺の追加によって最も外側の外部端子が連結になったら重み 2 の辺をサブ回路に追加する。重み 2, 3, 4, ... と追加していく。
こうしてすべての辺を追加すると森構造になっている。求めるべき深さは2頂点間のパスの最大重みである。森の中で2頂点の連結性や、パスの最大重みを求める問題は難しくない。
辺を追加すると外部端子を含む連結成分の数が減るので辺の追加は K * S 回以下。連結成分を DSU データ構造で管理して O((N+M+Q) log N) 時間のアルゴリズムができる。
コード
C++11
#include<stdio.h> #include<vector> using namespace std; typedef vector<int> VI; #define REP(i,n) for(int i=0, i##_len=(n); i<i##_len; ++i) #define EACH(i,c) for(__typeof((c).begin()) i=(c).begin(),i##_end=(c).end();i!=i##_end;++i) template<class T> inline void amin(T &x, const T &y) { if (y<x) x=y; } template<class T> inline void amax(T &x, const T &y) { if (x<y) x=y; } int N, K, S, M; vector<pair<int, int> > E[100011]; int out[100011]; int cost[100011]; int par[100011]; int height[100011]; int depth[100011]; int root(int v) { while (par[v] != -1) v = par[v]; return v; } void MAIN() { scanf("%d%d%d%d", &N, &K, &S, &M); REP (i, M) { int x, y; scanf("%d%d", &x, &y); x--; y--; E[0].emplace_back(x, y); } REP (i, N) { par[i] = -1; height[i] = 0; if (i < K) out[i] = i; else out[i] = -1; } VI ord; REP (t, N) { EACH (e, E[t]) { int x = e->first; int y = e->second; int rx = root(x); int ry = root(y); if (rx == ry) continue; if (out[rx] != -1 && out[ry] != -1) { for (int s=1; s<=S; s++) { E[t+1].emplace_back(s * K + out[rx], s * K + out[ry]); } } if (height[rx] >= height[ry]) { if (height[rx] == height[ry]) height[rx]++; par[ry] = rx; cost[ry] = t; amax(out[rx], out[ry]); ord.push_back(ry); } else { par[rx] = ry; cost[rx] = t; amax(out[ry], out[rx]); ord.push_back(rx); } } } for (int i=ord.size(); i--;) { int v = ord[i]; depth[v] = depth[par[v]] + 1; } int Q; scanf("%d", &Q); REP ($, Q) { int x, y; scanf("%d%d", &x, &y); x--; y--; int rx = root(x); int ry = root(y); if (rx == ry) { int ans = 0; while (x != y) { if (depth[x] < depth[y]) { amax(ans, cost[y]); y = par[y]; } else { amax(ans, cost[x]); x = par[x]; } } printf("%d\n", ans); } else { puts("-1"); } } } int main() { MAIN(); return 0; }
実装の工夫
DSU trees (Union-Find) を作るときにパス圧縮をしない、これは DSU の森構造をクエリに使うため。ただし、マージするときに高さを見てマージした後の高さが低くなるようにする (Weighted heuristic)。この木は高さが O(log n) なのでクエリのLCAを求めたり、パスを歩くのも愚直にやっても O(log n) で都合がよい。
もっと工夫するならば
DSU のパス圧縮をして高速化してクエリ用の木は別に作る。クエリパートは高さ O(log n) の木でダブリングする。すると全体で O(M + (N+Q) log log N) 、おそらく。ただしこれはオーバーキルな解法。
