yukicoder : No.1990 Candy Boxes

考察を丁寧に加えていくと解ける。
https://yukicoder.me/problems/no/1990

問題

N要素の整数列A,Bがある。
Aは初期状態で全要素0であり、Bは入力で与えられる。
A[i]とA[i+1]の偶奇が一致するようなiを選び、A[i]とA[i+1]を同時にインクリメントする、という手順を繰り返し、AをBにできるか。

解法

まず各iを選ぶ回数を求めよう。
B[i]=(iを選ぶ回数)+(i-1を選ぶ回数)であり、かつi=0を選ぶ回数はB[0]で確定するので、選ぶ回数は全部確定できる。

まず、A[i]とB[i]の偶奇を最小操作回数で揃えることを考える。
これをA[i]≦B[i]をキープしたまま達成すれば、最終的にA[i]=B[i]を達成できる。

C[i]=(A[i]+i)%2、D[i]=(B[i]+i)%2とする数列C,Dを考える。
iを選ぶ処理は、C[i]とC[i+1]をswapする処理といえる。
そこで、最小処理回数でA,Bの偶奇をそろえるには、C[i]とD[i]のうち1となっている箇所が等しくなければならず、また互いに総swap回数が減るように1をswapで動かしていこう。
C[x]=1にある1をD[y]=1まで持っていくには、(x＜yなら)i=x,x+1,...,y-1と順次選択すればよい。

複数の1の対応関係について、累積和を使い上記選択数の総和を取れば、A[i]とB[i]の偶奇をそろえるまでの最小操作回数がわかる。

int N;
int B[202020];
int D[202020];
int A[202020];
int add[202020];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	int pre=0;
	vector<int> X,Y;
	FOR(i,N) {
		cin>>B[i];
		D[i]=(B[i]+i)%2;
		A[i]=B[i]-pre;
		
		if(i%2) X.push_back(i);
		if(D[i]%2) Y.push_back(i);
		
		pre=A[i];
	}
	if(A[N-1]) {
		cout<<"No"<<endl;
		return;
	}
	if(X.size()!=Y.size()) {
		cout<<"No"<<endl;
		return;
	}
	FOR(i,X.size()) {
		add[min(X[i],Y[i])]++;
		add[max(X[i],Y[i])]--;
	}
	FOR(i,N) {
		if(i) add[i]+=add[i-1];
		if(A[i]<add[i]) {
			cout<<"No"<<endl;
			return;
		}
	}
	cout<<"Yes"<<endl;
	
}

まとめ

2つ連続した値を同時に操作する問題は、階差数列を取ってみたり、1要素ごとに偶奇反転させるとうまくいくケースが多いよね。