[AtCoder] ABC136 E – Max GCD (500点)

2020年1月26日AtCoder操作,最大公約数,不変量,最大値,500点,約数

問題へのリンク

問題概要

N 個の整数列 \(A_1, A_2, \cdots, A_N\) に、以下の操作をK回まで行う。これら全てはある数の倍数となるが、その数の最大値を求めよ。

操作：\(A_1, A_2, \cdots, A_N\)から異なる2つを選び、片方を-1, もう片方を+1する

制約

\begin{align}
&2 \leq N \leq 500\\
&1 \leq A_i \leq 10^6\\
&0 \leq K \leq 10^9
\end{align}

考え方

ステップ１

操作を行う問題なので、まずは操作をしても不変な量に注目してみると良いです。今回は、\(A_1, A_2, \cdots, A_N\)の合計値が、何回操作を行っても不変となります。

最適な操作を行ったとすると、全ての数が答え d の倍数になっているはずなので、合計値も d の倍数になるはずです。

つまり、答えは合計値の約数のうちのどれかになります。なので d を全探索して、条件に合うものの中から最大のものを出力すればACとなります。

ステップ2(dを固定したときに条件を満たすか判定）

\(A_1, A_2, \cdots, A_N\)を全て d の倍数にするために、最小で何回の操作を行う必要があるかを求めることができれば、この数がK以下の時に d は条件を満たします。

ここで
$$r_i := A_i \% d \hspace{15pt} (i=1,2,3 \cdots , n)$$
とすると、\(A_i\)が d の倍数になるためには

  1. \(A_i\)から\(r_i\) 回引く
  2. \(A_i\)に \(d- r_i\)回足す
  3. もしくは 1. の後に、d の倍数回引く
  4. もしくは 2. の後に、d の倍数回足す

のどれかになるはずです。

操作の特性を考えると、

m 回操作を行う \(\Leftrightarrow\) 引く回数の合計,足す回数の合計はともに m

を満たしています。

これを踏まえると、3.と4. の場合は 操作の回数を減らして 1.や2. に帰着させることができます。

例えば、m回の操作で全体が d の倍数となったとします。具体的に \(A_i\)から\(r_i + d\)回だけ引いていた時を考えて見ましょう。
引いていた分、他のどこか\(A_j\)で足していた部分があるはずです。この時、その足した回数は\((d\cdot k- r_j)\)になるはずです(kは1以上の整数)。
しかし、\(A_i\)を引いた数が d 少なく、\(A_j\)を足した回数が d 少ない時を考えると、m-d 回の操作で全体が d の倍数になります。

正確な証明はもう少し大変なので省略しますが、以上により\(A_i\)が d の倍数になるためには

  1. \(A_i\)から\(r_i\) 回引く
  2. \(A_i\)に \(d- r_i\)回足す

の時のみを考えるだけで良いです。

先に全てを \(r_i\) 回引くことにして、いくつかを \(d- r_i\)回足すことに変更して辻褄を合わせることを考えます。すると\(A_i\)を変更する時は、全体の引いた回数は \(r_i\) 小さくなり、足した回数は \(d- r_i\) だけ大きくなります。引いた回数と足した回数の差は

$$ r_i + (d – r_i) = d$$

だけ縮むことになります。これは i の選び方に依りません。最終的に、引く回数の合計,足す回数の合計が等しくなれば、条件に合います。

この時、なるべく\(r_i\) が大きいものを\(d- r_i\)回足すことにしてやると、操作回数が最小になって嬉しいです。

以上を踏まえると操作の最小回数は以下のように貪欲でわかります。

  1. \(r_1, r_2, \cdots, r_n\) は昇順にソートされているとする
  2. \(r_1\)からはじめて、\(A_i\)を\(r_i\) 回引くと決める
  3. 右から、2. で引いた分と辻褄を合わせるように\(A_j\)を \(d – r_j\)回足す
  4. d が条件を満たすならば、2.と3. を繰り返すと\(r_1, r_2, \cdots, r_n\) のどこか中間で、引いた分と足した分の合計が一致し、操作回数はK以下になる。一致しなければ d は条件を満たさない。

実際には累積和などを用いて計算することになりますが、このような選び方が最小の操作回数です。

気持ち的にはなんとなく貪欲で解けそうなのは分かりますが、実際に証明しようとすると難しい問題でした。

解き方

\(A_1, A_2, \cdots, A_N\)の合計値の約数が答えの候補です。これを d として条件に合うか全探索します。

条件に合うかは以下の計算をすればよいです。

$$r_i := A_i \% d \hspace{15pt} (i=1,2,3 \cdots , n)$$

を計算してこれを昇順にソートします。仕切りを i 番目と i+1番目の間に入れて、

  • 左側：\(r_1\)~\(r_i \) の和 \(L_i\)
  • 右側：\((d-r_{i+1})\)~\((d-r_{N}) \)の和 \(R_i\)

が一致するような i があれば、操作によって\(A_1, A_2, \cdots, A_N\)を全て d の倍数にすることができ、その操作の最小回数は \(L_i (= R_i )\) になります。

解答例

#include <bits/stdc++.h>
#define LOOP(n) for (int _i = 0; _i < (n); _i++)
#define REP(i, n) for (int i = 0; i < (n); ++i)
#define FOR(i, r, n) for (int i = (r); i < (n); ++i)
#define ALL(obj) begin(obj), end(obj)
using namespace std;
using ll = long long;
using ull = unsigned long long;
vector<long long> divisor(long long n) {
    vector<long long> ret;
    for (long long i = 1; i * i <= n; i++) {
        if (n % i == 0) {
            ret.push_back(i);
            if (i * i != n) ret.push_back(n / i);
        }
    }
    sort(ret.begin(), ret.end(), greater<long long>());
    return ret;
}

int main() {
    int N, K;
    cin >> N >> K;
    vector<int> A(N);
    int sum = 0;
    REP(i, N) {
        cin >> A.at(i);
        sum += A[i];
    }
    auto d = divisor(sum);  // 合計値の約数

    vector<int> r(N);
    REP(i, d.size()) {
        REP(j, N) { r[j] = A[j] % d[i]; }
        sort(ALL(r));
        vector<int> L(N + 1), R(N + 1);
        L[0] = 0;
        R[N] = 0;
        REP(j, N) { L[j + 1] += r[j] + L[j]; }
        for (int j = N - 1; j >= 0; j--) {
            R[j] += (d[i] - r[j]) + R[j + 1];
        }
        REP(j, N + 1) {
            if (L[j] == R[j] && L[j] <= K) {
                cout << d[i] << endl;
                return 0;
            }
        }
    }

    cout << N << endl;
    return 0;
}

AtCoder操作,最大公約数,不変量,最大値,500点,約数