AtCoder ARC #198 : C - Error Swap

どうにか解けた。
https://atcoder.jp/contests/arc198/tasks/arc198_c

問題

N要素の整数列A,Bが与えられる。
Aの2要素A[i],A[j] (i＜j)を選び、A[i]:=A[j]-1、A[j]:=A[i]+1とする処理(エラー付きswap)を同時に行える。
この処理を31000回まで行い、A=Bとできるか。できるなら一例を示せ。

解法

同じ2要素を2連続処理しても元に戻るだけ。
よって、N=2の時は、処理を0回/1回行ってA=Bにできるか判定する。

N≧3の場合、sum(A)=sum(B)なら解がある。
まず、先頭2要素以外、後ろから順に要素をそろえよう。

今n+1要素以降はA[i]=B[i]となっており、A[n]＜B[n]なものをA[n]=B[n]にしたいとする。
A[i]とA[n]をswap後、A[i]とA[i+1]とのエラー付きswapをiをインクリメントしながら行うと、A[n]を(N-i+1)だけインクリメントできる。
これを繰り返し、A[n]=B[n]にしよう。
A[n]＞B[n]も逆回しにすればよい。

残り2要素の場合だが、4回エラー付きswapを行うと、A[0]とA[1]の片方をインクリメント、片方をデクリメントすることができる。
これを繰り返してA=Bにしよう。

int N;
int A[101],B[101];
vector<int> E[2][2];

vector<pair<int,int>> ret;
void go(int a,int b) {
	assert(a<b);
	ret.push_back({a+1,b+1});
	swap(A[a],A[b]);
	A[a]--;
	A[b]++;
	int i;
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	x=0;
	FOR(i,N) {
		cin>>A[i];
		x+=A[i];
	}
	FOR(i,N) {
		cin>>B[i];
		x-=B[i];
		E[A[i]%2][B[i]%2].push_back(i);
	}
	if(x) {
		cout<<"No"<<endl;
		return;
	}
	
	if(N==2) {
		if(A[0]!=B[0]) {
			go(0,1);
		}
		if(A[0]!=B[0]) {
			cout<<"No"<<endl;
			return;
		}
	}
	else {
		for(i=N-1;i>=2;i--) {
			while(A[i]!=B[i]) {
				x=A[i]-B[i];
				if(x>0) {
					int ma=min(x+1,i);
					FOR(j,ma) {
						go(i-1-j,i-j);
					}
					go(i-ma,i);
					continue;
				}
				if(x<0) {
					int ma=min(abs(x)+1,i);
					go(i-ma,i);
					FOR(j,ma) {
						go(i-ma+j,i-ma+j+1);
					}
				}
			}
		}
		while(A[0]<B[0]) {
			go(0,1);
			go(0,2);
			go(1,2);
			go(0,2);
		}
		while(A[0]>B[0]) {
			go(1,2);
			go(0,2);
			go(1,2);
			go(0,1);
		}
	}
	
	
	FOR(i,N) assert(A[i]==B[i]);
	cout<<"Yes"<<endl;
	cout<<ret.size()<<endl;
	FORR2(a,b,ret) cout<<a<<" "<<b<<endl;
		
}

まとめ

手間取りはしたものの、まぁ解けて良かったね。