Codeforces Round #500 (Div. 2) D. Chemical table

考えたこと

sampleを眺める
1列を埋めたあと1つもない列に1個ずつ配置すると最適な置き方な気がした
列iに要素がa[i]個あるときh-max(a[i])個で1列埋めたくなる
列iと列jに同じ行の要素があるとき、この2つの列はマージできる
ある行について列jにあって列iにない要素とかがあると列iの行にも要素を生成できる
条件を満たす列をマージしていきたいのでUFを使って管理する
マージされた列で要素がある行の数を数えたい
マージするたびその連結成分でだぶってるのが1つ増える
このだぶりを管理しておいて最終的な連結成分の要素数からだぶりを引く
各連結成分で要素がある行の数が判明した
h-max個で1列を埋めて1つもない列に1つずつ配置していくみたいなのを書く
これを行と列反転して同じことをする
落ちる、考えてると以下のようなケースでだめなことに気づく

要素数が2以上の連結成分とマージするのに1個でできるので得している
h - (連結成分の要素数の和 - (連結成分数-1)) 個の要素を配置して1列を埋めたあと1つも無い列に配置していく
同じテストケースで落ちる
-----コンテスト終了-----
(y,x)が入力されたとき行yと列xをマージする
連結成分数-1 が答え

初動の方針は合ってるけど明らかに詰めるパートの方針を間違えている
値が合わなくて2時間迷うならさすがに考え直すべき
落ちるケースがqが大きいケースだったみたいで手元でつくるケースは通ってたっぽい
marukaiteとか2次元グリッドで行と列をつなげるグラフ作るのかなりよくあるパターンなんだしさすがに考えるべきだった

ソースコード

#include <bits/stdc++.h>

using namespace std;
using ll = long long;
#define int ll

#define FOR(i, a, n) for (ll i = (ll)a; i < (ll)n; ++i)
#define REP(i, n) FOR(i, 0, n)

class UnionFind {
public:
  const static int MAX_N = 400010;
  int par[MAX_N];
  int s[MAX_N];
  UnionFind() { init(); }
  UnionFind(int n) { init(n); }
  void init() { for(int i=0; i<MAX_N; ++i) par[i] = i, s[i] = 1; }
  void init(int n) { for(int i=0; i<n; ++i) par[i] = i, s[i] = 1; }
  int find(int x) {
    if(par[x] == x) return x;
    return par[x] = find(par[x]);
  }
  void unite(int x, int y) {
    x = find(x);
    y = find(y);
    if(x == y) return;
    if(s[x] < s[y]) par[x] = y, s[y] = s[x] + s[y];
    else par[y] = x, s[x] = s[x] + s[y];
  }
  bool same(int x, int y) { return find(x) == find(y);}
};
UnionFind uf;

signed main(void)
{
  cin.tie(0);
  ios::sync_with_stdio(false);

  int h, w, q;
  cin >> h >> w >> q;
  REP(i, q) {
    int x, y;
    cin >> y >> x;
    x--, y--;
    uf.unite(y, x+h);
  }
  int ret = 0;
  REP(i, h+w) if(uf.find(i) == i) ret++;
  cout << ret - 1 << endl;

  return 0;
}

ferinの競プロ帳

競プロについてのメモ

Codeforces Round #500 (Div. 2) D. Chemical table

考えたこと

ソースコード