kmjp's blog

競技プログラミング参加記です

AtCoder ABC #136 : E - Max GCD

Eは良かったんだけどDとFがグダったね。
https://atcoder.jp/contests/abc136/tasks/abc136_e

問題

N要素の整数列Aが与えられる。
任意の2要素を選び、片方をインクリメント、もう片方をデクリメントする、ということを最大K回行えるとする。
途中数列の要素が0や負になってもよい。

この時、GCDを最大いくつにできるか。

解法

まず、あり得るGCDはsum(A)の約数である。
よって、そのような約数を総当たりし、K回以内の処理で条件を満たせるか判定しよう。

例えば今GCDをDにできるか判定することを考えよう。
元の整数列Aに対し、B[i]=A[i] mod Dで求められる数列Bを考えよう。
Bの要素をいくつかデクリメントして0にし、残りをインクリメントしてDにすることを考えると、Bのうち小さいものをデクリメントし、大きいものをインクリメントすると少ない処理回数で条件を満たせそうというのがわかる。

よって、Bを昇順ソートし、prefixをデクリメント、suffixをインクリメントするとき、その必要回数の大きい方の最小値がK未満か判定していけばよい。

int N,K;
int A[505];
int S;

int hoge(int v) {
	vector<ll> V;
	vector<ll> SS;
	int i;
	FOR(i,N) V.push_back(A[i]%v);
	sort(ALL(V));
	SS.push_back(0);
	FORR(v,V) SS.push_back(SS.back()+v);
	
	FOR(i,N) {
		ll A=SS[i];
		ll B=(N-i)*1LL*v-(SS[N]-SS[i]);
		
		if(max(A,B)<=K) return 1;
	}
	return 0;
	
	
	
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>K;
	FOR(i,N) {
		cin>>A[i];
		S+=A[i];
	}
	int ret=0;
	for(x=1;x*x<=S;x++) if(S%x==0) {
		if(hoge(x)) ret=max(ret,x);
		if(hoge(S/x)) ret=max(ret,S/x);
	}
	cout<<ret<<endl;
	
}

まとめ

Dがグダったのもったいないなぁ。