Pinely Round 3 : D. Split Plus K

最後ラスト1分で通していた回。
https://codeforces.com/contest/1909/problem/D

問題

整数列Aと、整数値Kが与えられる。
A中の1要素xを選び、Aからxを取り除いて、y+z=x+Kとなる正整数y,zをAに追加することを考える。
Aの全要素を一致できるか。できるなら最小操作回数を答えよ。

解法

xがK未満・K・K以上であるとき、xとKの平均値は変わらずK未満・K・K以上である。
よって、Aの各要素がK未満・K・K以上のいずれかであるとして、2つ以上混ざっていると一致させるのはできない。

仮に全要素K未満の場合、Aの各要素のKとのさのGCDをgとするとき、各要素をK-gにするまでの操作回数を求めればよい。

int T;
ll N,K,A[202020];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>T;
	while(T--) {
		cin>>N>>K;
		vector<ll> D;
		int m=0;
		FOR(i,N) {
			cin>>A[i];
			D.push_back(abs(K-A[i]));
			if(A[i]<K) m|=1;
			if(A[i]>K) m|=2;
			if(A[i]==K) m|=3;
		}
		sort(A,A+N);
		if(A[0]==A[N-1]) {
			cout<<0<<endl;
			continue;
		}
		
		if(m==3) {
			cout<<-1<<endl;
			continue;
		}
		sort(ALL(D));
		ll g=0;
		FORR(d,D) g=__gcd(d,g);
		if(g==0) {
			cout<<0<<endl;
			continue;
		}
		ll ret=0;
		FORR(d,D) ret+=d/g-1;
		cout<<ret<<endl;
		
		
	}
}

まとめ

適度に考察要素と実装要素があってこの難易度帯としては手ごろな問題。