AtCoder Grand Contest 002: D - Stamp Rally
http://agc002.contest.atcoder.jp/tasks/agc002_d
解法
二分探索をすることを考えてみよう。すると i 番目までの辺を使った UnionFind が欲しくなる。でもあらかじめ全部作るのは難しい。 そこで Parallel Binary Search という手法を使う(Parallel Binary Search という名前が正しいかはよく分からない)。
動作の雰囲気をシミュレーションしたものを以下のページに置いといた。javascript の canvas で作っているので、IE のバージョン次第では見れないかも。
https://pekempey.github.io/parallel_binary_search/simulate.html
i 番目までの辺を使った UnionFind を全部作るのは難しいと言ったが、これを可能にするのが永続 Union Find。
半永続(最新版しか更新できない)であれば更新時間の配列を使って簡単に実装できる。
本番中自分が投げたのは完全 16 分木の永続配列を用いた全永続(最新版以外の更新も可能)の Union-Find。計算量とメモリの効率が良くないのだが、直感的なのでこっちを使ってる。
コード中で i 番目までの UnionFind を ufs[i] に入れるというコードを書いている。
vector<UnionFind> ufs(m + 1); UnionFind uf(n); for (int i = 0; i < m; i++) { int a, b; scanf("%d %d", &a, &b); a--; b--; uf.merge(a, b); ufs[i + 1] = uf; }
コードを見れば分かるように、見た目上はコピーが高速な UnionFind である。
8 分木に変えた実装が以下のコード。大体 1583 ms (111,872 KB)。2 分木でも高速な実装をすれば早くなるかな。