Codeforces Global Round 1 : E. Magic Stones

これは日本人へのボーナス問題。
https://codeforces.com/contest/1110/problem/E

問題

整数列Cが与えられる。
両端以外の任意の要素C[i]について、C[i]=C[i+1]+C[i-1]-C[i]で置き換えるということを行う。
同じ要素数の整数列Tに対し、上記操作を繰り返してCをTにできるか判定せよ。

解法

隣接要素に影響を受ける数列の操作を考える際は、隣接要素間の差分を取るというテクがある。
すると、今回の操作は差分列において要素をswapする操作と言える。
よって、CとTの先頭要素が等しく、かつ差分列を並べ替えると互いに一致させられるなら、CをTにできる。

関連問題には以下がある。
AtCoder AGC #006 : C - Rabbit Exercise - kmjp's blog
第5回 ドワンゴからの挑戦状 本戦 : B - XOR Spread - kmjp's blog

int N;
ll C[101010],T[101010];
vector<int> CC,TT;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,N) cin>>C[i];
	FOR(i,N) cin>>T[i];
	FOR(i,N-1) CC.push_back(C[i+1]-C[i]);
	FOR(i,N-1) TT.push_back(T[i+1]-T[i]);
	sort(ALL(CC));
	sort(ALL(TT));
	if(CC==TT && C[0]==T[0] && C[N-1]==T[N-1]) {
		cout<<"Yes"<<endl;
	}
	else {
		cout<<"No"<<endl;
	}
}

まとめ

これのおかげかなんか今回日本人の成績よかったよね。