Codeforces #802 : Div2 F. Puzzle

こっちはコードが短い。
https://codeforces.com/contest/1700/problem/F

問題

0/1が各マスに格納された、2*Nのグリッドが2つ与えられる。
前者について隣接2マスの要素を入れ替えることを繰り返し、後者と一致させたい。
最小何回行えばよいか。

解法

Prefixを見ていく。
上段下段それぞれ、前者と後者のグリッドにおける1の数の累積和の差を考える。
この絶対値分は、まず確定でswapが生じる。
加えて、両絶対値の小さい方の分もswapが生じる。

int N;
int A[2][202020];
int B[2][202020];
int C[2][202020];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,N) cin>>A[0][i];
	FOR(i,N) cin>>A[1][i];
	FOR(i,N) cin>>B[0][i];
	FOR(i,N) cin>>B[1][i];
	int U=0,D=0;
	ll sum=0;
	FOR(i,N) {
		U+=A[0][i]-B[0][i];
		D+=A[1][i]-B[1][i];
		x=min(abs(U),abs(D));
		if(U>0&&D<0) {
			sum+=x;
			U-=x;
			D+=x;
		}
		if(U<0&&D>0) {
			sum+=x;
			U+=x;
			D-=x;
		}
		sum+=abs(U)+abs(D);
	}
	if(U||D) {
		cout<<-1<<endl;
	}
	else {
		cout<<sum<<endl;
	}
	
}

まとめ

こういうのJOIとかにありそうなイメージ。