AtCoder ARC #152 : C - Pivot

割と好調だった回。
https://atcoder.jp/contests/arc152/tasks/arc152_c

問題

ソート済みの整数列Aが与えられる。
Aの要素を1つ選び、その値をsとする。
A[i]=2*s-A[i]で置き換える作業を各A[i]に一斉に行う。

この作業をAが負にならないように繰り返したとき、Aの最大値を最小化せよ。

解法

Aの差のGCDをgとすると、偶数回処理を行うと、Aの各値を2gだけずらすことができる。
これによりA[0]を負にならない範囲で2gずつ減少させよう。

処理回数が全体で奇数の場合と偶数の場合をそれぞれ考えると良い。

int N;
ll A[202020];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,N) cin>>A[i];
	ll mi=1LL<<60;
	FOR(i,2) {
		ll g=0;
		FOR(j,N-1) g=__gcd(g,A[j+1]-A[j]);
		g=2*g;
		ll a=A[0]/g*g;
		mi=min(mi,A[N-1]-a);
		
		a=A[N-1];
		FOR(j,N) A[j]=2*a-A[j];
		reverse(A,A+N);
	}
	cout<<mi<<endl;
}

まとめ

これは本番もかなりあっさり思いつけたな。