Codeforces #648 Div2 F. Swaps Again

Div2回で7問もあるの珍しいよね。
http://codeforces.com/contest/1365/problem/F

問題

N要素の整数列A,Bが与えられる。
Aのうち範囲が重複しないよう、prefixとsuffixを同じ数選んでswapする、という処理を繰り返す。
AをBにできるか判定せよ。

解法

A中の各要素について、Aの中心で反転した位置の要素の値は、swap処理を繰り返しも変わらない。
また、そのような位置関係にある2要素を反転させることも任意でできる。

そこで、(A[i],A[N-1-i])のunorderedなペアの集合が、(B[i],B[N-1-i])のunorderedなペアの集合と一致するか確認すればよい。

int T,N;
int A[505],B[505];


void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>T;
	while(T--) {
		cin>>N;
		FOR(i,N) cin>>A[i];
		FOR(i,N) cin>>B[i];
		if(N%2==1 && A[N/2]!=B[N/2]) {
			cout<<"No"<<endl;
			continue;
		}
		
		map<pair<int,int>,int> M;
		FOR(i,N/2) {
			x=A[i];
			y=A[N-1-i];
			M[{min(x,y),max(x,y)}]++;
		}
		FOR(i,N/2) {
			x=B[i];
			y=B[N-1-i];
			if(M[{min(x,y),max(x,y)}]==0) break;
			M[{min(x,y),max(x,y)}]--;
		}
		
		if(i<N/2) cout<<"No"<<endl;
		else cout<<"Yes"<<endl;
		
		
	}
		
}

まとめ

Div2のFにしては簡単。