Codeforces #899 : Div2 E2. Two Permutations (Hard Version)

割と苦戦してるな。
https://codeforces.com/contest/1882/problem/E2

問題

1～NのPermutation Pと、1～MのPermutation Qが与えられる。
以下のクエリを繰り返し、P,Qを最短手で同時に昇順にソートせよ。

• 2つのindex i, jを選ぶ。
  • P[0...(i-1)]とP[(i+1)....(N-1)]を入れ替える。
  • Q[0...(j-1)]とQ[(j+1)....(N-1)]を入れ替える。

解法

f(n) := n手でPをソートできる手段があれば、その手順
g(m) := m手でQをソートできる手段があれば、その手順

とすると、f(i)もg(i)も存在するような最小のiを求めればよい。
f(n)やg(m)が存在するならf(n+2)やg(m+2)も存在する。(同じiやjを2連打すればよい)
また、f(n+N)やg(m+M)も存在する。(i=1やj=1をN回・M回選択すればよい)

以後、Pをソートすることを考える。
Pの先頭にXという仮要素を加える。以後、Xが移動した場合も、XがPの先頭であるということにする。
iを選択するということは、XとP[i]をswapするのに等しい。
これを利用し、最終的なXの場所を総当たりしながらそれぞれの最小swap回数とその手順を求めればよい。

int N,M;
int A[2525],B[2525];
vector<int> X[10101];
vector<int> Y[10101];

vector<int> hoge(vector<int> T,int X) {
	int A[2525],R[2525];
	int i,j;
	FOR(i,T.size()) {
		A[i]=(T[i]+X)%T.size();
		R[A[i]]=i;
	}
	vector<int> ret;
	int cur=0;
	while(A[X]!=X) {
		int x=R[cur];
		ret.push_back((x-cur+T.size())%T.size());
		swap(A[x],A[cur]);
		R[A[cur]]=cur;
		R[A[x]]=x;
		swap(cur,x);
	}
	
	FOR(i,T.size()) if(A[i]!=i) {
		ret.push_back((i-X+T.size())%T.size());
		swap(A[i],A[X]);
		R[A[i]]=i;
		R[A[X]]=X;
		int cur=i;
		while(A[X]!=X) {
			int x=R[cur];
			ret.push_back((x-cur+T.size())%T.size());
			swap(A[x],A[cur]);
			R[A[cur]]=cur;
			R[A[x]]=x;
			swap(cur,x);
		}
	}
	return ret;
		
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>M;
	FOR(i,N) cin>>A[i];
	FOR(i,M) cin>>B[i];
	X[0]=Y[0]={1};
	
	FOR(i,N+1) {
		vector<int> Z={0};
		FOR(j,N) Z.push_back(A[j]);
		auto a=hoge(Z,i);
		X[a.size()]=a;
	}
	FOR(i,M+1) {
		vector<int> Z={0};
		FOR(j,M) Z.push_back(B[j]);
		auto a=hoge(Z,i);
		Y[a.size()]=a;
	}
	
	if(X[0].empty()&&Y[0].empty()) {
		cout<<0<<endl;
		return;
	}
	if(X[0].empty()) {
		X[2]={1,N};
		X[N].clear();
		FOR(i,N) X[N].push_back(1);
	}
	if(Y[0].empty()) {
		Y[2]={1,M};
		Y[M].clear();
		FOR(i,M) Y[M].push_back(1);
	}
	
	const int ma=5000;
	for(i=1;i<=ma;i++) {
		if(X[i].size()&&Y[i].size()) {
			cout<<i<<endl;
			FOR(j,i) cout<<X[i][j]<<" "<<Y[i][j]<<endl;
			return;
		}
		if(X[i].size()&&X[i+2].empty()) {
			X[i+2]=X[i];
			X[i+2].push_back(1);
			X[i+2].push_back(N);
		}
		if(Y[i].size()&&Y[i+2].empty()) {
			Y[i+2]=Y[i];
			Y[i+2].push_back(1);
			Y[i+2].push_back(M);
		}
		if(X[i].size()&&i+N<=ma&&X[i+N].empty()) {
			X[i+N]=X[i];
			FOR(j,N) X[i+N].push_back(1);
		}
		if(Y[i].size()&&i+M<=ma&&Y[i+M].empty()) {
			Y[i+M]=Y[i];
			FOR(j,M) Y[i+M].push_back(1);
		}
	}
	
	cout<<-1<<endl;
	
}

まとめ

仮の要素を入れるの賢いな…。