kmjp's blog

競技プログラミング参加記です

Codeforces #692 Div1 A. Peaceful Rooks

ABEと変なACの取り方した回。
https://codeforces.com/contest/1464/problem/A

問題

N*Nのチェス盤に、M個のルークがある。
これらは互いに1手で相手の駒を取れない位置にある。

各ルークを動かし、それぞれ左上から右下に並ぶ対角線上に乗せたい。
最小何手かかるか。

解法

各ルーク、1手で移動できる対角線上のマスは最大2個ある。
Union-findを使い、同じ目的地の対角線上のマスを共有するものをグループにしよう。

もしx個のルークのグループで、1手で移動できる対角線上のマスの総数がx個なら、それらを並べるのにx+1手かかる。
もしx個のルークのグループで、1手で移動できる対角線上のマスの総数がx個より多いなら、それらを並べるのにx手かかる。

int T;
int N,M;
vector<int> E[101010];
int X[101010],Y[101010];

template<int um> class UF {
	public:
	vector<int> par,rank,cnt;
	UF() {par=rank=vector<int>(um,0); cnt=vector<int>(um,1); for(int i=0;i<um;i++) par[i]=i;}
	void reinit(int N) {int i; FOR(i,N) rank[i]=0,cnt[i]=1,par[i]=i;}
	int operator[](int x) {return (par[x]==x)?(x):(par[x] = operator[](par[x]));}
	int count(int x) { return cnt[operator[](x)];}
	int operator()(int x,int y) {
		if((x=operator[](x))==(y=operator[](y))) return x;
		cnt[y]=cnt[x]=cnt[x]+cnt[y];
		if(rank[x]>rank[y]) return par[x]=y;
		rank[x]+=rank[x]==rank[y]; return par[y]=x;
	}
};
UF<101010> uf;
set<int> C[101010];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>T;
	while(T--) {
		cin>>N>>M;
		uf.reinit(N);
		FOR(i,N) E[i].clear(),C[i].clear();
		FOR(i,M) {
			cin>>X[i]>>Y[i];
			X[i]--;
			Y[i]--;
			if(X[i]==Y[i]) {
				i--;
				M--;
				continue;
			}
			E[X[i]].push_back(i);
			E[Y[i]].push_back(i);
		}
		
		FOR(i,N) if(E[i].size()==2) uf(E[i][0],E[i][1]);
		FOR(i,M) {
			C[uf[i]].insert(X[i]);
			C[uf[i]].insert(Y[i]);
		}
		int ret=0;
		FOR(i,M) if(uf[i]==i) {
			if(C[i].size()==uf.count(i)) ret+=uf.count(i)+1;
			else ret+=uf.count(i);
		}
		cout<<ret<<endl;
	}
}

まとめ

500ptでもいい気はするけどね。