Soxy Log

競技プログラミングに関すること

AtCoder ABC136 E - Max GCD

問題


AtCoder ABC136 E - Max GCD

解法


Aの要素を全て割り切る整数の候補は、A[i]の総和Sの約数である。
これらをd[i]とすると、全てを試してもたかだかO(sqrt(N * max(A)))個であるので時間内に計算を終えることができる。
d[i]でA[j]を割った余りをa[j]とすると、aの要素同士で題意の操作を行い、K回以内に全てのa[i]をd[i]の倍数にできるかを判定すればよい。
a[i]を昇順にソートした配列と、1つの仕切りを考える。
仕切りより左のj個のa[i]の和をsum_left、右のN-j個のd[i]-a[j]の和をsum_rightとすると、abs(sum_left - sum_right)がd[i]の倍数となるときのsum_rightが、全てのAをd[i]の倍数にするための操作回数である。
仕切りの位置をずらしていくことで、全てのAをd[i]の倍数にする為の最小操作回数が求まる。
これを全てのd[i]に対して行うことでdの最大値を求めればよい。

ソースコード

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int main()
{
    int N;
    ll K;
    cin >> N >> K;
    vector<ll> A(N);
    ll S(0);
    for(int i(0);i<N;++i){
        cin >> A[i];
        S += A[i];
    }
    vector<ll> d;
    for(int i(1);i*i<=S;++i){
        if(S % i == 0){
            d.push_back(i);
            d.push_back(S/i);
        }
    }
    int M = d.size();
    vector<ll> a(N);
    ll a_sum,sum_left,sum_right,target_d,d_max(0);
    for(int i(0);i<M;++i){
        target_d = d[i];
        a_sum = 0;
        for(int j(0);j<N;++j){
            a[j] = A[j] % target_d;
            a_sum += a[j];
        }
        sort(a.begin(),a.end());
        sum_left = a_sum;
        sum_right = 0;
        ll swap_num = 1e18;
        for(int j(N-1);j>=0;--j){
            sum_left -= a[j];
            sum_right += target_d-a[j];
            if(abs(sum_left - sum_right) % target_d == 0) swap_num = min(swap_num, max(sum_left, sum_right));
        }
        if(swap_num <= K) d_max = max(d_max, target_d);
    }
    cout << d_max << endl;
    return 0;
}