AtCoder Beginner Contest 120

皆さま、お久しぶりです。

競プロを再開したいと思います。

C - Unification

考えたこと：

（これやったことあるんだけど忘れたので、もう一度解く・・・）

・再帰でいじる。

ー＞ダメ。計算が間に合わない。

・貪欲

ー＞前から順番に消せるなら消していく方法で大丈夫？

ー＞ダメ。計算が間に合わない。

理由：

...1111111110000000...のような並びだと

１周毎に２個しか減らないので最悪計算量Ｏ（Ｎ＾２）になる。

解法：

最終形を考えるとすぐに解けた。

最終的な形。すなわち、もうこれ以上キューブを取り除けない形はどうなっているか？

答え：（0または1のみ）または（全て消えている）形

ex)00000,111111

理由： 

0と1がともに存在すると仮定し、これ以上キューブを取り除けないとする。

この時、0と1が隣り合わせになる部分が少なくとも１つ存在する。

これはキューブがこれ以上取り除けないことに矛盾する。

（証明終了）

よって、取り除けるキューブの個数はmin(0の個数、1の個数）*２となる。

int main() {
  string s;
  cin >> s;
 
  int a = 0, b = 0;
  for (int i = 0; i < s.size(); i++) {
    if (s[i] == '0')
      a++;
    else
      b++;
  }
 
  cout << 2 * min(a, b) << endl;
  return 0;
}

D - Decayed Bridges

考えたこと：

・「便利さ」を行き来できる点の組の個数と定義する。

・橋が全てある時の、行き来できる点の組の個数は

Ｎコンビネーション２＝Ｎ＊（Ｎ－１）/ 2　（＝allとする）

（以後,calc(x)=x*(x-1)/2とする。）

であるから、「不便さ」＝all　-「便利さ」と表せる。

・「便利さ」＝　Σ calc(連結な点の集合の要素数)

で表せるため、「不便さ」を求めるよりも求めやすそう。

・便利さを求めるうえで、橋を削っていくよりも、無から橋を付け加えていく方が考えやすそう。

・連結な点の集合を管理するにはUnion-Find を使えば良さそう。

ー＞しかし、私のUnion-Findには要素数を返す関数は搭載されていない。

（以前、要素数をrank()にしてもいけると聞いたことがあったので、ちゃんと調べておけばよかったと後悔）

ー＞mapを使って、集合の親に対して集合の要素数を返すように管理すればいいのではないか？

これらのことを踏まえて、解答に移る。

・橋をＮ番目から１番目に向かって「追加」していく。

・点aと点bをつなぐ橋を追加するとき、

１）（点aと連結な集合Ａ）と（点bと連結な集合Ｂ）が連結でないとき

ＡとＢを　unite()　結合して集合Ｃとし、集合の要素数を管理するmapを変更する。

具体的に、

map[Ｃの親]＝map[Aの親]＋map[Bの親]　とする。

（ここでmap[集合の親]＝（集合の要素数）を表すことに注意すること。また、あらかじめmap[１～Ｎ]＝１と初期化しておくこと。）

２）ＡとＢが連結なとき

Ｃ内で橋を追加しただけなので、集合の要素数に変化はない。

これで集合の要素数の管理は順に出来るようになったが、このままではＭ回、全頂点Ｎ個を調べることになってしまい計算量Ｏ（ＭＮ）。間に合わない。

しかし、よくよく考えると橋を追加したときに、便利さに変化があるのは

集合の要素数が変化した部分のみであるから、頂点aと頂点bに関係する部分だけを考えて、１つ前の便利さから変化させればよい。

ここで、便利さをsubとすると、

２）のときsubに変化はない。

１）のときsub += calc(Cの要素数) - (calc(Aの要素数)+calc(Bの要素数))

となる。これは、ＡとＢの２つの集合から、Ｃという１つの集合に変化したときの便利さの差分を足している。

以上から、便利さを求める計算量は　Ｏ（log N)

（mapの使用がネックになっている）

よって全体計算量はO(M log N) <= 5*10^5となり間に合う。

解法：

struct UnionFind {
  vector<int> par;
  vector<int> rank;

  UnionFind(int n = 1) {
    init(n);
  }

  void init(int n = 1) {
    par.resize(n);
    rank.resize(n);
    for (int i = 0; i < n; ++i) par[i] = i, rank[i] = 0;
  }

  int root(int x) {
    if (par[x] == x) {
      return x;
    } else {
      int r = root(par[x]);
      return par[x] = r;
    }
  }

  bool same(int x, int y) {
    return root(x) == root(y);
  }

  bool unit(int x, int y) {
    x = root(x);
    y = root(y);
    if (x == y) return false;
    if (rank[x] < rank[y]) swap(x, y);
    if (rank[x] == rank[y]) ++rank[x];
    par[y] = x;
    return true;
  }
};

int N, M;
vector<P> query;
vector<int> ans;
UnionFind uf(101010);
map<int, int> mp;

int calc(int x) {
  return x * (x - 1) / 2;
}

signed main() {
  cin >> N >> M;
  for (int i = 0; i < M; i++) {
    int a, b;
    cin >> a >> b;
    a--, b--;
    query.push_back(P(a, b));
  }

  reverse(ALL(query));

  for (int i = 0; i < N; i++) mp[i] = 1;

  int sub = 0;
  for (int i = 0; i < M; i++) {
    P p = query[i];
    int a = p.first, b = p.second;

    if (!uf.same(a, b)) {
      int x = mp[uf.root(a)], y = mp[uf.root(b)];
      uf.unit(a, b);
      mp[uf.root(a)] = x + y;

      sub += calc(x + y) - calc(x) - calc(y);
      ans.pb(calc(N) - sub);
    } else {
      int x = mp[uf.root(a)];
      uf.unit(a, b);
      mp[uf.root(a)] = x;

      ans.push_back(calc(N) - sub);
    }
  }

  reverse(ALL(ans));

  for (int i = 1; i < M; i++) cout << ans[i] << endl;
  cout << calc(N) << endl;
  return 0;
}

感想：

無事全完できて良かったです。

ＢとＣはもう少し速く解きたかったですね。