AtCoder ARC #126 : C - Maximize GCD

概ねレート通りだった回。
https://atcoder.jp/contests/arc126/tasks/arc126_c

問題

整数列Aが与えられる。
1つの要素を選びインクリメントすることを、最大K回行える。
このとき、全要素のGCDの最大値はいくつか。

解法

Aの全要素をK回以内の操作で最大値にそろえることができるなら、全要素同じ値にすることでGCDを最大化できる。
以下そうでない場合を考える。

以下の2値を計算しておこう。
f(x) := Aのうちx以下の要素の個数
g(x) := Aのうちx以下の要素の総和

GCDをxにするとき、K回以内で達成できるかを、x=2～(max(A)-1)の範囲で総当たりしよう。
整数aに対し、Aのうち(ax+1)～(a+1)xの範囲の値をxの倍数にするには、(f*1*(a+1)x-(g*2 回だけインクリメントが必要である。
aを総当たりしてインクリメントの必要回数を求めよう。

int N;
ll K;
ll A[303030];

ll num[603030],sum[603030];

void solve() {
	int i,j,k,l,r,x,y;
	
	cin>>N>>K;
	ll s=0;
	ll ma=0;
	FOR(i,N) {
		cin>>A[i];
		s+=A[i];
		ma=max(ma,A[i]);
		num[A[i]]+=1;
		sum[A[i]]+=A[i];
	}
	for(i=1;i<=602020;i++) {
		num[i]+=num[i-1];
		sum[i]+=sum[i-1];
	}
	
	
	ll lef=1LL*N*ma-s;
	if(lef<=K) {
		cout<<(s+K)/N<<endl;
		return;
	}
	int ret=1;
	for(i=2;i<=ma;i++) {
		ll need=0;
		for(x=0;x<=ma;x+=i) {
			ll nu=num[x+i-1]-num[x];
			ll su=sum[x+i-1]-sum[x];
			need+=nu*(x+i)-su;
		}
		if(need<=K) ret=i;
	}
	
	cout<<ret<<endl;
}

まとめ

これは割とすんなり思いついた。

*1:a+1)x)-f(ax

*2:a+1)x)-g(ax