ICPC2020 国内予選 F - 避難所

ICPC2020 国内予選の F 問題「避難所」の解説です。よく見る解法とは違うアプローチで解いたため、せっかくなので解説記事にしてみました。

問題概要

$n$ 頂点 $m$ 辺 ( $1\le n,m\le 10^5$ ) の連結で単純な無向グラフ $G$ が与えられる。また、各辺 $E_i$ には値 $A_i$ ( $1\le A_i\le 10^5$ )が割り当てられている。
ここで、 $G_c$ を辺集合 $\{E_i|c\lt A_i\}$ から構成されるグラフとする（つまり、値 $c$ 以下の辺を除いたグラフ）。
また、 $f_{G,i}(c)$ を $G_c$ において頂点 $i$ を含む連結成分の個数として定義し、頂点 $i$ について列 $[f_{G,i}(0),f_{G,i}(1),f_{G,i}(2)\cdots]$ を考えた時、これを辞書順最大にするような $i$ を全て求めよ。

愚直解法

まずは、それぞれの列を愚直に生成することを考えます。なお、この問題は、時刻 $t$ にて $A_i=t$ なる辺 $E_i$ をグラフから削除していった時の列とも捉えられるため、今後はそのように捉えます。
削除操作を逆順に見て復元することを考えると、順に頂点を繋ぐクエリになりそうです。よって、異なる連結成分が繋がれて連結成分のサイズが変化した時に全ての頂点についての列を更新すれば良さそうです。これには、それぞれの連結が完了した時点で任意の頂点を含む連結成分の個数を求められれば良いです。これは UnionFind と呼ばれているデータ構造により実現可能で、この解法の計算量は $O(n^2a(n))$ ( $a(n)$ はアッカーマン関数の逆関数)になります。

考察

ここで、以下のようなケースを観察します。このケースにて、頂点 $1$ が解となることはあるでしょうか?
f:id:keymoon:20201120181338p:plain
少し考えると、これは解にはならないことが分かります。なぜならば、 $c\le 99$ の時までは連結だったので列 $1,2,3$ は $c=99$ までは等しく、 $c=100$ でサイズ $1$ とサイズ $2$ の連結成分に分かれたために頂点 $1$ の属するサイズ $1$ の頂点集合の列はサイズ $2$ の頂点集合に属する頂点の列より小さくなるからです。
復元を考える際にもこの観察は役立ちます。サイズ $a$ の頂点集合とサイズ $b$ の頂点集合をマージする際、 $a\gt b$ ならば $a$ に含まれる頂点のみが解の候補で、 $a\lt b$ ならば $b$ に含まれる頂点のみが解の候補となります。また、 $a=b$ ならば両方の集合に含まれる頂点が解の候補となります。これを全てのマージについて繰り返すことで、最終的に残った頂点が解となることが分かります。よって、それぞれの連結成分において、解の候補とその候補について復元された列を一つだけ持っておけば良いことになります。

また、先程の解法において復元の都度にそれぞれの頂点について列を更新していますが、この操作は非常に無駄が多そうです。なので、更新があった場所のみ更新してあげることを考えます。そうすると、それぞれの列は $[[1,1,1,1],[2,2],[3,3,3,3,3]]$ のような区間の列に分けられることが分かります。(実際のデータとしては、 $[(1,4),(2,2),(3,5)]$ といった形で持ちます。)このような形で表した列同士の比較は、通常の列と同じ要領で最初から走査することでできることが分かります。そのため、今後はこのような形で表した列のみ考えることにします。

このような改善をした際、復元パートの計算量はどうなっているでしょうか?2つの列について比較をする際、比較回数は2つの列の長さのうち短い方に比例します。なぜならば、順々に見てどちらかの列が終端に達した場合、それ以降は比較ができないので比較が終了するためです。それぞれの列の長さは最悪 $O(n)$ になるので、 $n$ 回のマージについて最悪 $O(n^2)$ となっているように思えます。しかし、実際はもう少し良い見積もりができます。

まず、それぞれの列に新しく要素を追加する際、「定数の計算量を前払い」することを考えます。後々重い操作をする際に、今貯金した計算量を消費することで均しでの計算量を保証しようという考えです。この貯金した計算量を「ポテンシャル」と呼ぶことにします。追加する要素に「ポテンシャル」というチップを一枚ずつ並べて配置する例えが分かりやすいでしょうか。
これを踏まえて、比較の際には辞書順で小さい方の列の方のポテンシャルを消費することとします。(ポテンシャルはあくまでも計算量を解析する際の概念的なものなので、比較する前から大小を考えて良いです。) 列の比較は長さの小さい方に比例するということを思い出すと、 $\min(|a|,|b|)\le |a|$ より、もし全ての要素にポテンシャルが残っていた場合、それらによって比較の計算量を払いきれることが分かります。また、比較をした後には辞書順で小さい列を削除して大きい列のみ残すため、残っている全ての要素にポテンシャルがついている状態を維持することができます。よって、この「要素の追加/比較/マージ」の手続を繰り返すことで復元を完了することができ、これについては要素の追加回数の定数倍しかかからないことが分かりました。要素の追加は全グループの初期化時と連結成分を繋いだ時にしか発生しないために $O(n)$ 回しか発生しません。また、解の候補の保持に連結リスト等を用いるとリストの連結や走査が $O(1)$ でできるようになるので、辺のソートを除いた計算量は $O(m\cdot a(n)+n)$ となります。辺のソートを考えた際は $O(m\log(m)+m\cdot a(n)+n)$ となりますが、今回の問題では辺のコストにも小さい制約があるため、バケツソートを使って $O(\max(A)+m\cdot a(n)+n)$ としても間に合います。

実装

少しだけ重めです。ソートは $\log$ をつけました。列の持ち方や比較方法については解説とは少し違った持ち方をしています。UnionFind は型 T とマージする関数 T& merge(T&, T&) をテンプレートに渡し、マージしたら内部で勝手にデータをマージするものです。（merge の中で引数いじって戻り値にしているの、未定義を踏んでいそうなのでくわしいひと教えて下さい……）
提出
$O(\max(A)+m\cdot a(n)+n)$ 版: 提出

#include <bits/stdc++.h>
using namespace std;

template<class T, T& (*merge)(T&, T&)>
struct UnionFind{
  vector<T> data;
  vector<int> parent;
  vector<int> size;
  
  UnionFind(vector<T> &v): data(v), parent(v.size()), size(v.size(), 1){
    iota(parent.begin(), parent.end(), 0);
  }
  
  T& operator[](int i){return data[find(i)];}
  int find(int x){
    return x == parent[x] ? x : parent[x] = find(parent[x]);
  }
  bool unite(int x, int y){
    int xp = find(x), yp = find(y);
    if (xp == yp) return false;
    if (size[xp] < size[yp]) swap(xp, yp);
    parent[yp] = xp;
    data[xp] = merge(data[xp], data[yp]);
    size[xp] += size[yp];
    return true;
  }
};

const int INF = INT32_MAX / 2;
struct Group{
  using P = pair<int, int>;

  //{(1,2),(2,5),(5,6)}: 1が2まで, 2が5まで, 5が6まで
  //0 1 2 3 4 5 6
  //-------------
  //1 1 1 2 2 2 5
  vector<P> data;
  list<int> cand;
  Group(){}
  Group(int i): data{P(INF, 1)}, cand{i}{}

  void add(int at, int num){
    if (data.back().first == at){
      data.back().second = num;
    }
    else{
      data.emplace_back(at, num);
    }
  }
  //グループのサイズ
  int cnt(){
    return data.back().second;
  }
  // a < b -> -1
  // a > b -> 1
  static int compare(Group& a, Group& b){
    int cur = 0;
    int aind = a.data.size() - 1;
    int bind = b.data.size() - 1;
    while (0 <= aind && 0 <= bind){
      int apos = a[aind].first, bpos = b[bind].first;
      int aval = a[aind].second, bval = b[bind].second;
      if (aval == bval){
        //aの方が先に変わる→aの方が小さい(狭義単調減少性より)
        if (apos < bpos) return -1;
        if (apos > bpos) return 1;
      }
      else{
        //aの方が値が小さい→aの方が小さい
        if (aval < bval) return -1;
        if (aval > bval) return 1;
      }
      aind--; bind--;
    }
    return 0;
  }

  P operator[](int k){return data[k];}
};

int current;
Group& merge(Group& l, Group& r){
  int cnt = l.cnt() + r.cnt();
  l.add(current, cnt);
  r.add(current, cnt);

  int cmp = Group::compare(l, r);
  // l < r
  if (cmp < 0) return r;
  // l > r
  if (cmp > 0) return l;
  if (cmp == 0){
    l.cand.splice(l.cand.end(), move(r.cand));
    return l;
  }
  assert(false);
}

struct Edge{
  int from;
  int to;
  int value;
  Edge(){}
  Edge(int from, int to, int value): from(from), to(to), value(value) {}
};

bool solve(){
  int n, m;
  cin >> n >> m;
  if (n == 0) return false;
  vector<Edge> edges{}; edges.reserve(m);
  for (int i = 0; i < m; i++){
    int a, b, s;
    cin >> a >> b >> s;
    a--, b--;
    edges.emplace_back(a, b, s);
  }
  sort(edges.begin(), edges.end(), [](Edge a, Edge b){
    return a.value > b.value;
  });
  vector<Group> groups{}; groups.reserve(n);
  for (int i = 0; i < n; i++) groups.emplace_back(i);

  UnionFind<Group, merge> uf(groups);
  for (auto&& edge : edges){
    int s = edge.from, t = edge.to, c = edge.value;
    current = c;
    uf.unite(s, t);
  }
  
  vector<int> res(uf[0].cand.begin(), uf[0].cand.end());
  sort(res.begin(), res.end());
  for (int i = 0; i < res.size(); i++){
    if (i != 0) cout << ' ';
    cout << res[i] + 1;
  }
  cout << '\n';
  return true;
}

int main(){
  cin.tie(nullptr);
  ios::sync_with_stdio(false);
  while (solve());
  return 0;
}