AtCoder Begginer Contest #014 D.閉路
問題概要
- N個の頂点からなる木が与えられる（辺はN-1個）
- グラフは単純（自己辺、多重辺を含まない）である
- 辺の長さは1
- Q個のクエリ(a, b)が与えられるので、頂点aとbを結んだときに出来る閉路の長さを求めよ。
制約
- 1<=N<=100000
- 1<=Q<=100000
解法
頂点aとbを結んだときに出来る閉路の長さは、aとbの最短距離に1を足したものと等価。
また、適当に根sを定め、sから見た頂点iの深さをdepth[i]とすると、
任意の頂点aとbの最短距離は、
depth[a] + depth[b] - 2 * depth[aとbの最も近い共通の親]
となる。（ここまで本番中に考察できた）
問題は、「aとbの最も近い共通の親」をどのようにして求めるか、である。
これは、LCA(Lowest Common Ancestor)という有名問題らしい。
LCAはダブリングによって効率的に求めることができる。
ダブリングについてはこちらから。
http://kakira.hatenablog.jp/entry/2014/09/16/201532
f : V→V(Vは頂点集合)をv∈Vについて、f(v) := vの親 とする。
ただし、vが根の場合、f(v) = -1。
fを2^k回試行した後の値をdp[k][v]の配列に格納するとすると、
dp[k + 1][v] = dp[k][f[k][v]];
が成り立つ。
k = 0のときのdp[0][v]は深さ優先探索で調べればOK。
aとbの最も近い共通の親を求めたいときは以下のようにする。
- depth[a]とdepth[b]を比較して、深い方を浅い方の深さに揃える
- 揃えるときは、depth[深い方] - depth[浅い方]回だけfを試行すればよいので、前回の記事のように実行してみる
- もし揃え終わった後、aとbが既に共通になっていれば、a(またはb)を返す
- kの降順ループについて、aとbのそれぞれについて、2^k回fを試行した結果を考える
- もし、試行した結果が同じ頂点なら、それよりも前（またはそれ自身）が最も近い親なので、何もしない
- もし、試行した結果が違う頂点なら、それよりも後に最も近い親がいるので、aとbを2^k回fを試行した後の頂点に変える。
- (このループは、降順で実行しているため、ループが終わるとaとbは必ず最も近い親の一つ前の子になる
- 最後に、dp[0][a](またはdp[0][b])つまり、aの一つ上の親を返して終わり。
ダブリングが分かっていればそこまで難しくはない。
が、細かいチェックがあるので油断すると死。
覚えておくべきこと
今回のように、LCAは閉路の長さを求めるのにも使えるが、やはり一番使えるのは最短距離。
depth[a] + depth[b] - 2 * depth[aとbの最も近い共通の親]の公式と合わせて覚えておこう。
つまづいたところ
- ダブリングを知らなかった
- 前回のエントリーの方が後に解いた問題です
- LCAを知らなかった
感想
- 非常にためになる問題でした。
ソースコード
#include <map> #include <set> #include <list> #include <cmath> #include <queue> #include <stack> #include <cstdio> #include <string> #include <vector> #include <complex> #include <cstdlib> #include <cstring> #include <numeric> #include <sstream> #include <iostream> #include <algorithm> #include <functional> #define mp make_pair #define pb push_back #define all(x) (x).begin(),(x).end() #define rep(i,n) for(int i=0;i<(n);i++) using namespace std; typedef long long ll; typedef unsigned long long ull; typedef vector<bool> vb; typedef vector<int> vi; typedef vector<vb> vvb; typedef vector<vi> vvi; typedef pair<int,int> pii; const int INF=1<<29; const double EPS=1e-9; const int dx[]={1,0,-1,0},dy[]={0,-1,0,1}; std::vector<pii> e[100000]; std::vector<int> depth(100000, -2); int dp[17][100000]; int n; void dfs(int v, int dep, int parent) { depth[v] = dep; dp[0][v] = parent; for (int i = 0; i < e[v].size(); ++i) { if (depth[e[v][i].second] != -2) continue; dfs(e[v][i].second, dep + 1, v); } } int getV(int v, int dep) { int now = v; int i = 0; do { if (dep % 2 == 1) { now = dp[i][now]; } dep /= 2; i++; } while(dep != 0); return now; } int main(int argc, char const *argv[]) { cin >> n; for (int i = 0; i < n - 1; ++i) { int a, b; cin >> a >> b; a--, b--; e[a].push_back(mp(a, b)); e[b].push_back(mp(b, a)); } dfs(0, 0, -1); for (int k = 1; k < 17; ++k) { for (int v = 0; v < n; ++v) { if (dp[k - 1][v] == -1) { dp[k][v] = -1; } else { dp[k][v] = dp[k - 1][dp[k - 1][v]]; } } } int Q; cin >> Q; for (int i = 0; i < Q; ++i) { int u, v; int ans = 0; cin >> u >> v; u--, v--; int u_ = u, v_ = v; if (depth[u] > depth[v]) {swap(u, v);} ans += depth[v] - depth[u]; v = getV(v, depth[v] - depth[u]); if (v == u) { cout << ans + 1 << endl; continue; } for (int k = 16; k >= 0; --k) { if (dp[k][v] == dp[k][u]) {continue;} //cout << "debug : " << k << endl; v = dp[k][v]; u = dp[k][u]; } int p = dp[0][v]; ans = depth[u_] + depth[v_] - 2 * depth[p] + 1; cout << ans << endl; } return 0; }
AtCoder Begginer Contest #013 D.阿弥陀
問題概要
N本の縦線とM本の横線で構成されたあみだくじがある。
(M本の横線の位置の情報が与えられる。)
このくじをD個縦につなげたとき、
左からi番目(1<=i<=Nを満たすi全て)の縦線を選ぶと
最終的にどこにたどり着くかそれぞれ答えなさい。
制約
- 2<=N<=10^5
- 0<=M<=2*10^5
- 1<=D<=10^9
解法
まず「D=1について左からi番目を選ぶとどこに飛ぶか」という対応表を作る。
ここから、D回地道にシュミレーションすると、1回のシュミレーションにO(D)かかる。
これをN回(iの範囲分)繰り返すので、O(ND)となってしまい、TLE。
そこで、「D=2^iについてj番目を選ぶとどこに飛ぶか」という対応表dp[i][j]を考える。
この配列の大きさは、NlogDとなる。
この対応表を埋めるとき、i=0については、D=1の場合と同様。
iとi+1番目について、
dp[i + 1][j] = dp[i][dp[i][j]];
が成り立つ。
(内側のdp[i][j]で移動した先を入力として、さらに移動させている。こうすると、2^i回のみに限るが、
効率よく場所を計算することが出来る。)
こんな感じに、2^n回の操作の移動先を2^(n-1)回の操作の移動先から求めることをダブリングというらしい。
これが求まってしまえば、後はDを２進数表記で解釈して、操作をしていけば良い。
（D=7なら、4回操作→2回操作→1回操作をすれば良い）
計算量はO(NlogD)。
もっと一般的に
ある写像f:A→Aがあるとき、fをD回掛けた結果を素早く求めるときは
先程のようなテーブルを取ると良い。
今回の写像は、左からi番目と右からj番目を対応づける写像。
また、一般的な木（グラフ理論の木）について、
f(v):V→Vを「f(v) : vの親」と定義すると、これもこのテクニックを使うことが出来る。
（具体的には、LCA(Lowest Common Ancestor)などで使える。）
つまずいたところ
- 移動先をもとめるときに、横棒は逆順から適用していかないとダメ
- 普通の順番で適用すると、「下側のi番目に上側の何番目が入るか」を求めてしまう
- 求めるべきは「上側のi番目が下側の何番目に入るか」である
- dpの配列の大きさを間違えた
- なぜかDが10万だと思ってたり、Nが1万だと思ってたり
- D回適用するところで、now = [j][i]; とやってしまった
- 8回移動したのを「取り消して」、16回移動…
感想
- ダブリングはかなり一般的に使えそうな気がした。
- 解いてて面白かったです。(小並感)
#include <map> #include <set> #include <list> #include <cmath> #include <queue> #include <stack> #include <cstdio> #include <string> #include <vector> #include <complex> #include <cstdlib> #include <cstring> #include <numeric> #include <sstream> #include <iostream> #include <algorithm> #include <functional> #define mp make_pair #define pb push_back #define all(x) (x).begin(),(x).end() #define rep(i,n) for(int i=0;i<(n);i++) using namespace std; typedef long long ll; typedef unsigned long long ull; typedef vector<bool> vb; typedef vector<int> vi; typedef vector<vb> vvb; typedef vector<vi> vvi; typedef pair<int,int> pii; const int INF=1<<29; const double EPS=1e-9; const int dx[]={1,0,-1,0},dy[]={0,-1,0,1}; const int MAX_LOG_V = 30; int dp[MAX_LOG_V][100001] = {0}; bool comp(pii a, pii b) { return a.second < b.second; } int main(int argc, char const *argv[]) { int n, m, d; cin >> n >> m >> d; for (int i = 0; i < 100001; ++i) { dp[0][i] = i; } std::vector<int> v; for (int i = 0; i < m; ++i) { int a; cin >> a; a--; v.push_back(a); } for (int i = v.size() - 1; i >= 0; --i) { swap(dp[0][v[i]], dp[0][v[i] + 1]); } for (int i = 0; i < MAX_LOG_V - 1; ++i) { for (int j = 0; j < n; ++j) { dp[i + 1][j] = dp[i][dp[i][j]]; } } for (int i = 0; i < n; ++i) { int d_ = d; int now = i; int j = 0; do { if (d_ & 1) { now = dp[j][now]; } d_ >>= 1; j++; } while(d_ != 0); cout << now + 1 << endl; } return 0; }
テスト
テスト投稿です。
