kmjp's blog

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

Codeforces #564 Div1 D. Nauuo and Portals

これはパズルっぽい問題。
https://codeforces.com/contest/1172/problem/D

問題

N*Nのグリッドがある。
ここで、セルを2つ選びワープ装置の両端を配置する、ということを任意に行えるとする。
ただし1セルに2個以上の装置は配置できない。

ワープ装置のあるセルに対し、隣接セルから人が進入してきたとする。
するとその人は、対応する反対側の装置のあるセルに移動し、向きは変わらずそのまま歩いていく。

ここで2N人の人がいるとする。
うち1~N番目の人はi番目の行の左端から右向きにグリッドに進入したところ、右側R[i]行目からグリッドを出た。
同様に(N+1)~(2N)番の人は(i-N)番目の列の上端から下向きにグリッドに進入したところ、下側C[i-N]列目からグリッドを出た。

条件を満たすワープ装置の配置を求めよ。

解法

端から徐々に問題空間を狭めていく。
まずi行目・i列目を確定することを考える。このiを1からNまで順に総当たりしていく。
横方向i行目から出ていく人がすでにi行目にいて、縦方向i列目から出ていく人がすでにi列目にいる場合は何もしない。
そうでない場合、i列目・i行目にワープ装置を1組置くと、今i行目にいないけどi行目に出ていかせたい人をi行目にワープさせ、同様に今i列目にいないけどi列目に出ていかせたい人をi列目にワープさせることができる。

int N;
int R[1010],C[1010];
int P[1010],Q[1010];
vector<vector<int>> V;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,N) {
		cin>>R[i];
		R[i]--;
		P[R[i]]=i;
	}
	FOR(i,N) {
		cin>>C[i];
		C[i]--;
		Q[C[i]]=i;
	}
	
	FOR(i,N) {
		if(P[i]==i && Q[i]==i) continue;
		for(y=i;y<N;y++) if(R[y]==i) break;
		for(x=i;x<N;x++) if(C[x]==i) break;
		if(y==i && x==i) continue;
		V.push_back({y,i,i,x});
		swap(R[y],R[i]);
		P[R[y]]=y;
		P[R[i]]=i;
		swap(C[x],C[i]);
		Q[C[x]]=x;
		Q[C[i]]=i;
	}
	
	cout<<V.size()<<endl;
	FORR(v,V) cout<<v[0]+1<<" "<<v[1]+1<<" "<<v[2]+1<<" "<<v[3]+1<<endl;
	
}

まとめ

一見O(N^2)に見えるが、O(N)で解ける。
ただそれはどうも単にvalidator側がO(N^2)かかるためのようで。