Codeforces #435 Div2 E. Mahmoud and Ehab and the function

よく意図がわからない問題。
http://codeforces.com/contest/862/problem/E

問題

N要素の整数列A[i]とM要素の整数列B[i]が与えられる。
f(j)は以下のように定義される。
C[i]=A[i]-B[i+j]とするN要素の数列としたとき、f(j)=|C[1]-C[2]+C[3]-...|である。
厳密には、である。

ここでQ個のクエリが与えられる。
各クエリは、A指定された区間の全要素に同じ値を加算するものである。
各クエリ後、f(j)の最小値を求めよ。

解法

各クエリ後A[1]-A[2]+A[3]-....の値がどうなるかは容易に求められる。
Aに対し、-B[i+j]+B[i+j+1]-B[i+j+2]-... の値のうち、上記値とできるだけ近い値を求められれば良いことになる。

よって、事前に-B[i+j]+B[i+j+1]-B[i+j+2]-...の候補を列挙しておけば、二分探索で容易に近い値を求められる。

int N,M,Q;
int A[101010],B[101010];
ll BS[101010];
vector<ll> cand;
void solve() {
	int i,j,k,l,r,x,y; string s;
	
	scanf("%d%d%d",&N,&M,&Q);
	ll sum=0;
	FOR(i,N) {
		scanf("%d",&A[i]);
		sum+=((i%2==0)?1:-1)*A[i];
	}
	FOR(i,M) scanf("%d",&B[i]);
	
	for(i=M-1;i>=0;i--) {
		BS[i]=B[i]-BS[i+1];
		if(i+N<=M) cand.push_back(BS[i]+((N%2==1)?BS[i+N]:-BS[i+N]));
	}
	sort(ALL(cand));
	cand.erase(unique(ALL(cand)),cand.end());
	
	while(1) {
		ll mi=1LL<<60;
		x=lower_bound(ALL(cand),sum)-cand.begin();
		for(i=max(0,x-2);i<min(x+3,(int)cand.size());i++) mi=min(mi,abs(sum-cand[i]));
		cout<<mi<<endl;
		
		if(Q==0) break;
		Q--;
		int L,R,X;
		scanf("%d%d%d",&L,&R,&X);
		if((R-L)%2==0) {
			if(L%2==0) sum-=X;
			else sum+=X;
		}
		
		
	}
	
}

まとめ

Dの方がはるかに面倒だった。