yukicoder : No.2821 A[i] ← 2A[j] - A[i]

これはすんなり解けた。
https://yukicoder.me/problems/no/2821

問題

整数列Aに対し、以下の手順を任意回数行えるとする。

• 添え字を2つi,jと選び、A[i]=2*A[j]-A[i]とする。

Aのk要素のprefixに対し、最大値と最小値の差を最小化したい。
各kに対しその値を答えよ。

解法

数直線上で考えると、この処理は座標A[i]にあった点をA[j]に対し対称な位置に移動することに相当する。
これを繰り返すと、最大値と最小値の差は、元の数列の差の最大公約数となる。

あとは、kを増やしながらこの最大公約数を更新していけばよい。

int N;
ll A[303030];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	ll g=0;
	FOR(i,N) {
		cin>>A[i];
		g=__gcd(g,abs(A[i]-A[0]));
		cout<<g<<endl;
		
	}
}

まとめ

数直線上の反転であることがすぐ思いつけたので良かったね。