問題概要

ボードの大きさW,Hであらわされる。そのボード内のどの位置にスライムがいるかのクエリが与えられる。スライムは一回の動作で上下左右にほかのスライムにぶつかるか、壁にぶつかるまで動くことが可能である。求める解はすべてのスライムを1つにくっつけるまでに何回スライムを動かす必要があるかを求める。

解法

1つのスライムに対して、そのスライムの上下左右にあるスライムの数をzとすると上下左右にあるスライムをz回の動作で一つのスライムにすることができる。だから、まずは、ボード内のすべてのスライムいっきにくっつけるのではなく（キングスライムを作るのではなく）、ミニキングスライムを作ることを考える。ミニキングスライム（連結結合をなしている集合の数）がいくつできるかを調べるには、unionfindのライブラリを用いればできる。具体的なやり方は「memoX[x座標]とmemoY[y座標]を利用する。この配列にはいままで見てきたスライムの中でx,y座標それぞれについて、一番初めに出てきた頂点の番号を座標に対してバケツソートで記録しておく。そのようにしておくことで、後でx,y座標のどちらか少なくとも一方の座標がすでに出ているスライムと一致したスライムが出てきたときに、unite(i, memoX[x])(x座標が一致する場合)することで、ミニキングスライムの要素をunionfind構造を利用して求めることができる。また、ミニキングスライムの個数を数える方法は、memoXに入っている頂点のルートの種類を調べれば、ミニキングスライムの個数を求めることができる。(memoYを調べる必要はない) 解答はn(スライムの数) - 1 + (ミニキングスライムの個数)で求まりそう。n - 1はキングスライムを作るために動かす総回数。mは連結成分を4方向の中から指定した壁に寄せるための回数（連結成分の数だけ壁に寄せる回数がかかるのは、もし連結成分内に指定した壁にくっついているキングスライムが2つ以上あるなら、その2つにキングスライムは一つのキングスライムにすることができているはずなので矛盾するから）。実際の答えを求めるには場合分けが必要。ミニキングスライムどおしは四方いずれかの壁を利用しなければ一つにすることはできない。そのため、スライムが少なくとも一つどこかの壁にあるか、ないかで場合分けが必要。1つでも壁にあれば、さらに-1すればいい（ミニスライムを壁にくっつけるために動かす回数がm-1回になる)。さらに、ミニキングスライムの数がただ1つの場合、壁に寄せる必要ががないため、n - 1で求まる。

ミス

ミニキングスライムの数を数える部分で、memoX[] != -1の数を調べてしまったので、ルートが同じ頂点を重複して考えてしまった。場合分けを間違えていた（ミニスライムが1つしかない場合を忘ていた）。

コード

#include <iostream>
#include <algorithm>
#include <vector>
#include <cstdio>
#include <cstdlib>
#include <set>
using namespace std;
#define rep(i,n) for(int i=0;i<(n);i++)

class DisjointSet{
    public:
        vector<int> rank, p;//rank:木の高さ p:親の頂点番号
        DisjointSet(){}
        DisjointSet(int size){//頂点の数
            rank.resize(size, 0);
            p.resize(size, 0);
            rep(i, size) makeSet(i);
        }
        void makeSet(int x){
            p[x] = x;
            rank[x] = 0;
        }
        //同じ木にあるか判定（今回使わない）
        bool same(int x, int y){
            return findSet(x) == findSet(y);
        }
        // 木どうしをくっつける
        void unite(int x, int y){
            link(findSet(x), findSet(y));
        }
        //木の高さを考慮して木どうしをくっつける
        void link(int x, int y){
            if(rank[x] > rank[y]){
                p[y] = x;
            }else{
                p[x] = y;
                if(rank[x] == rank[y]) rank[y]++;
            }
        }
        //親を探す（ルートまで）
        int findSet(int x){
            if(x != p[x]){
                p[x] = findSet(p[x]);
            }
            return p[x];
        }
};

int main(void){
    int n, w, h;
    bool cornerw = false, cornerh = false;//壁の端にスライムがあるかを記憶しておくフラグ
    cin >> n >> w >> h;
    //この二つの配列は、入れようと現在見ているスライムの列と行にすでにスライムが入っているかどうかを確かめるもの
    vector<int> memoX(w, -1);//列
    vector<int> memoY(h, -1);//行
    DisjointSet ds = DisjointSet(n);

    rep(i, n){
        int x, y;
        scanf("%d %d", &x, &y);
        x--; y--;//0origin
        if(x == 0 || x == w - 1) cornerw = true;
        if(y == 0 || y == h - 1) cornerh = true;
        //縦と横列で分けて並べおく
        //一つのスライムにつき同じx座標とy座標を共有するものはくっつつけることができる
        if(memoX[x] < 0) memoX[x] = i;//その列にまだスライムが入ったことなければX[列]=頂点番号　を入れる
        else ds.unite(i, memoX[x]);//すでにその列にスライムが入っていれば、そのスライムとくっつける
        if(memoY[y] < 0) memoY[y] = i;
        else ds.unite(i, memoY[y]);
    }

    set<int> sum;
    rep(i, w){
        if(memoX[i] != -1) sum.insert(ds.findSet(memoX[i]));//重複を許さないようにsetを利用
    }

    int m = sum.size();//連結成分（ミニキングスライム）の個数

    if(m > 1){
        if(cornerw == true || cornerh == true){
            printf("%d\n", n + m - 2);//壁にくっついている連結成分を1つ以上作れるので、さらに-1
        }else{
            printf("%d\n", n + m - 1);
        }
    }else{//ミニキングスライムが一つだけの時
        printf("%d\n", n - 1);
    }
    return 0;
}

srupのメモ帳

競プロで解いた問題や勉強したことを記録していくメモ帳

AOJ 2382 - King Slime

問題概要

解法

ミス

コード