反省

UnionFind木使うとかどうやったら思いつくんですかね…。

解説

参考: AtCoder ABC 131 F - Must Be Rectangular! (600 点) - けんちょんの競プロ精進記録

fn solve(xys: &[(usize, usize)]) -> usize {
    let n = xys.len();
    const MAX: usize = 110000;

    let uf = UnionFind::new(MAX * 2 + 1);

    let mut mx = vec![0; MAX * 2 + 1];
    let mut my = vec![0; MAX * 2 + 1];

    for &(x, y) in xys.iter() {
        uf.unite(x, y + MAX);
    }

    for i in 1..(MAX + 1) {
        mx[uf.root(i)] += 1;
        my[uf.root(i + MAX)] += 1;
    }

    let mut ans = 0;

    for i in 1..(MAX * 2 + 1) {
        ans += mx[i] * my[i];
    }

    ans - n
}

問題文にある操作が完了すると、長方形のグループがいくつか出来上がることになる。長方形の横の格子点数と縦の格子点数を掛けて（つまり長方形の）元の点の数を引けば、その長方形を作成する際に追加された点の数がわかる。

それを全長方形グループについて行うということは<長方形の格子点数> - Nを計算することになり、これが最後のans - nとなっている。

後は長方形グループを探せばよい。座標(x, y)をxとy+MAXの無効グラフとしてUnionFind木に登録していくことでこれを構築することができる。

mx[i]にはiをrootとする長方形グループに属するx座標の数、my[i]には同様にy座標の数が格納されるためmx[i] * my[i] で長方形に含まれる格子点の数が得られる。なお、iをrootとする長方形グループがない場合はmx[i] * my[i]は0となる。

papamitra

AtCoder ABC #131 F - Must Be Rectangular!

反省

解説