[AtCoder] AISing Programming Contest 2019 C – Alternating Path

2019年6月9日

問題

方針

各マスに番号を割り振る

\( H \) 行 \( W \) 列のマスを持つグリッドにおける \( i \) 行 \( j \) 列目のマスの番号を \( i \times W + j \) とします。このようにマスの番号を割り当てると \( 0 \) から \( HW – 1 \) までの範囲で一意に番号を持ちます。

パスの数を求める (深さ優先探索)

黒マスから白マスへのパスの数の合計を求めます。ただし、パスは黒白黒白黒…と交互に色が変わるパスとします。
ある黒マス \( B_i(x_i, y_i)\) を始点として、到達できる白マスと黒マスの数 \( w_i, b_i \) を求めます。このとき、始点の黒マスもカウントします。到達できるマスは全て連結されているので、任意の黒マスから任意の白マスへのパスが存在します。したがって、この連結において求めるパスの合計は \( w_ib_i \) となります。

パスの数を求める (Union Find)

ある要素がどのグループに属すかといった問題では、Union Find を使うことができます。Union Find については、下の記事がまとまっていると思います。

あるパスにおける白マスと黒マスの個数が分かればよいでの、Union Find を使ってそれらを求めます。

コード

提出したコード (深さ優先探索)

提出したコード (Union Find)

Union Find

class DisjointSet {
public:
  vector<int> p, rank, size;
  DisjointSet(int n) {
    p.assign(n, 0);
    rank.assign(n, 0);
    size.assign(n, 0);
    for (int i = 0; i < n; i++) {
      make_set(i);
    }
  }
 
  void make_set(int x) {
    p[x] = x;
    rank[x] = 0;
    size[x] = 1;
  }
 
  int find_set(int x) {
    if (x != p[x]) {
      p[x] = find_set(p[x]);
    }
    return p[x];
  }
 
  bool same(int x, int y) {
    return find_set(x) == find_set(y);;
  }
 
  int union_size(int x) {
    if (x != p[x]) {
      size[x] = union_size(find_set(x));
    }
    return size[x];
  }
 
  void link(int x, int y) {
    if(rank[x]  > rank[y]) {
        p[y] = x;
        size[x] = size[x] + size[y];
    }else if(rank[x] < rank[y]){
        p[x] = y;
        size[y] = size[x] + size[y];
    }else if(x != y) {
      p[y] = x;
      rank[x]++;
      size[x] = size[x] + size[y];
    }
  }
 
  void unite(int x, int y) {
      link(find_set(x), find_set(y));
  }
};