AtCoder: ABC136-E Max GCD (500) - ひらめの日常

問題はこちら

$A_1, A_2, ..., A_N$ から $i \neq j$ となる $A_i, A_j$ を選び、 $A_i = A _ i + 1, A_j = A _ j - 1$ とする。この時、 $K$ 以下の操作回数で $A$ の最大公約数として考えられるもののうち、最大のものを求めよ。

考え方

step1 - 解の候補

まず、 $A_i$ に+1して、 $A_j$ に-1するという操作は、 $A_i$ の値を一つ $A_j$ に移動する操作と考えることができる。

次に大事なのは、答えの候補は $A$ の和の約数 となること。これはなぜかを考えてみる。今、答えとなる最大の最大公約数を $x$ とする。

約数であるという性質から、 $A _ 1 \% x = A _ 2 \% x =...= A _ N \% x = 0$
modの性質から、 $(A _ 1 + A _ 2 + ... + A _ N ) \% x = 0$
今回の操作は片方に+1, もう片方に-1するだけなので、総和は操作終了後にも変わらない。
以上より、答えの候補は $A$ の和の約数となる。

なので、ある最大公約数 $x$ が $K$ 回以下の操作によって達成されるかをすべて確かめ、達成されるものの中で最大のものが答えとなる。

step2 - 達成可能かを確認する

$x$ で割ったあまりが小さい方（= $A_i$ ）から、大きい方（= $A_j$ ）へと渡すのが操作方法が少なくて良い方法だとわかる。 $A _ i \% x = a _ i$ , $A _ j \% x = a _ j$ , $a _ i \lt a _ j$ 　とおく。（簡単にするため、二つの数字でやり取りすることで割り切れる場合を考えてみる。）

$a_i$ から $a_j$ へ渡して $x$ で割り切れるようにする時。操作回数は $max(a _ i, x - a _ j)$
$a_j$ から $a_i$ へ渡して $x$ で割り切れるようにする時。操作回数は $max(a _ j, x - a _ i)$
$a _ i \lt a _ j$ より、 $max(a _ i, x - a _ j) \lt max(a _ j, x - a _ i)$

よって、 $x$ で割った余りを小さい順でsortして、インデックス $i$ より小さい側を渡す側。インデックス $i$ 以上を渡される側として、必要な操作回数が $K$ 以下であれば満たすと判定すれば良い。

解答

#include <bits/stdc++.h>

using namespace std;

using ll = long long;

#define rep(i, n) for(ll i = 0; i < (ll)(n); i++)
#define repr(i, n) for(ll i = ll(n - 1); i >= 0; i--)
#define each(i, mp) for(auto& i:mp)
#define all(obj) (obj).begin(), (obj).end()

/* ------------- ANSWER ------------- */
/* ---------------------------------- */
// 約数列挙
vector<ll> divisor(ll n) {
    vector<ll> res;
    for (ll i = 1; i * i <= n; ++i) {
        if (n % i == 0) {
            res.emplace_back(i);
            if (i != n / i) res.emplace_back(n / i);
        }
    }
    return res;
}

int main() {

    ll n, k;
    cin >> n >> k;
    vector<ll> a(n);
    rep(i, n) cin >> a[i];

    vector<ll> divs = divisor(accumulate(all(a), 0LL));

    ll ans = 0;
    each(e, divs) {
        vector<ll> mods(n);
        rep(i, n) mods[i] = a[i] % e;
        sort(all(mods));

        vector<ll> minus(n + 1);
        rep(i, n) minus[i + 1] = minus[i] + mods[i];

        vector<ll> plus(n + 1);
        repr(i, n) plus[i] = plus[i + 1] + e - mods[i];

        for (ll i = 0; i <= n; ++i) {
            if (max(plus[i], minus[i]) <= k) ans = max(ans, e);
        }
    }
    cout << ans << '\n';
    return 0;
}

Submission #7148617 - AtCoder Beginner Contest 136