Codeforces #1049 : Div2. F. Sum Minimisation

コードは短め。
https://codeforces.com/contest/2140/problem/F

問題

N要素の整数列Aが与えられる。
以下の処理を繰り返し、Aの総和をどこまで減らせるか判定せよ。

• Aのうち部分列を選ぶ。その要素数をKとする。
• そのK要素の総和をXとしたとき、Y=X%Kとする。選んだK要素のうち、小さい順にY個をデクリメントする。

解法

Aをソートしておく。
A[1]...A[N-1]に偶奇の異なる対があれば、そのどちらかとA[0]を選択することでA[0]を減らせる。
同様に、A[i]-A[0]が2～(N-1)のどれかで割り切れないならば、A[0]を減らせる。

もしA[0]を2回以上減らせる場合、さらに減らすことが可能なので、上記を2回試せばよい。

int T,N,A[1<<20];
ll sum;
int ok() {
	int i,j;
	if(N>=24) {
		FOR(i,N) if(A[i]!=A[0]) return 0;
	}
	else {
		for(j=2;j<=N-1;j++) {
			FOR(i,N) if(A[i]%j!=A[0]%j) return 0;
		}
	}
	if(sum%N) return 0;
	return 1;
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>T;
	while(T--) {
		cin>>N;
		sum=0;
		FOR(i,N) {
			cin>>A[i];
			sum+=A[i];
		}
		sort(A,A+N);
		
		if(ok()) {
			cout<<sum<<endl;
			continue;
		}
		A[0]--;
		sum--;
		if(ok()) {
			cout<<sum<<endl;
			continue;
		}
		cout<<-1<<endl;
	}
}

まとめ

Writerはイギリス英語使い？