C 問題としてはかなり難しいですね。

問題へのリンク

問題概要（一部意訳）

小さい飴は 1 個 $X$ 円、大きい飴は 1 個 $Y$ 円である（ $X \lt Y$ である）。

$N$ 人がいて、人 $i$ は、飴を合わせて $A_{i}$ 個買おうとしている。ただし、 $N$ 人全員の購入金額がちょうどぴったり一致するようにしなければならない。

$N$ 人による「大きい飴」の購入個数の総和の最小値を求めよ。

制約

$2 \le N \le 2 \times 10^{5}$
$1 \le A_{i}, X, Y \le 10^{9}$

ㅤ

考えたこと

この手の問題では、ある変数を決め打って考えてみるということがとても大切です。しかし、この問題では、どの変数を決め打つとよいかを見定めることが難しいですね。

たとえば、次のような方向性で考えてしまうと、ドツボにハマってしまいます。

「 $N$ 人それぞれの、小さい飴の個数と、大きい飴の個数を色々変えてみて、全員の購入金額が一致するように調整するにはどうしたら......」

そうではなく、今回は、次のように考えてみましょう。

$N$ 人全員の購入金額がちょうどぴったり一致すると言われているのだから、その金額を $P$ などと置いてみよう
そして、 $P$ を決め打って考えてみよう

なぜ、購入金額 $P$ を決め打つとよいかというと、 $P$ を決め打つと、それぞれの人が小さい飴と大きい飴を何個変えばよいのかが、一意に決まるのです！！！

まずは、このことを解明してみましょう！

ㅤ

購入金額を決め打ったときの、各人の購入金額

人 $i$ の、小さい飴の購入個数を $x_{i}$ 個、大きい飴の購入個数を $y_{i}$ 個としよう。このとき、次の方程式が立てられます。

$x_{i} + y_{i} = A_{i}$ （合計 $A_{i}$ 個買うことから）
$X x_{i} + Y y_{i} = P$ （合計金額が $P$ であることから）

これは、中2で学ぶ連立方程式です。これを解くと、次のようになります。

$\displaystyle x_{i} = \frac{Y A_{i} - P}{Y - X}$
$\displaystyle y_{i} = \frac{P - X A_{i}}{Y - X}$

なお、この方程式の解き方が分からないという方は、中2の教科書に解き方が載っているので、復習すると良いと思います（教科書に載っているのは $X, Y, P, A_{i}$ の部分が具体的な数字になっているようなものですが、それらが文字になっても解き方は一緒です）。

補足：この方程式が解けない人のための解き方

$x_{i} + y_{i} = A_{i}$ ...... ①
$X x_{i} + Y y_{i} = P$ ...... ②

とする。

① × $Y$ より

$Y X_{i} + Y y_{i} = Y A_{i}$ ...... ③

③ - ② より

$(Y - X) X_{i} = Y A_{i} - P$ ...... ③

よって

$\displaystyle x_{i} = \frac{Y A_{i} - P}{Y - X}$ ...... ④

④ を ① に代入して

$\displaystyle \frac{Y A_{i} - P}{Y - X} + y_{i} = A_{i}$

よって

$y_{i} = A_{i} - \displaystyle \frac{Y A_{i} - P}{Y - X}$ $= \displaystyle \frac{(Y - X) A_{i}}{Y - X} - \frac{Y A_{i} - P}{Y - X}$ $= \displaystyle \frac{Y A_{i} - X A_{i} - Y A_{i} + P}{Y - X}$ $= \displaystyle \frac{P - X A_{i}}{Y - X}$

ここで当然気になるのは、 $\displaystyle \frac{Y A_{i} - P}{Y - X}$ や $\displaystyle \frac{P - X A_{i}}{Y - X}$ って分数だけど大丈夫なの......？？というところでしょう。

他にも、 $P$ が大きすぎると $x_{i} = \displaystyle \frac{Y A_{i} - P}{Y - X}$ が負の値になってしまい、それもよくありません。私たちは購入価格 $P$ を決め打って考えてきましたが、 $P$ がなんでもいいというわけではないのです。

そこで、次に、 $P$ が満たすべき条件について考えてみましょう。

ㅤ

購入価格 $P$ が満たすべき条件

$P$ がなんでもいいというわけではありません。

まず、購入個数 $A_{i}$ の最小値を $m$ 、最大値を $M$ とするとき、 $P$ はどうあがいても $Ym$ より大きくすることはできません。購入個数が最も少ない人の立場で考えると、その人の購入金額を最大にするためには、すべて大きい飴を買うとよいですが、そのときの購入金額が $Ym$ 円だからです。

同様に、 $P$ はどうあがいても $XM$ より小さくすることはできません。購入個数が最も多い人の立場で考えると、その人の購入金額を最小にするためには、すべて小さい飴を買うとよいですが、そのときの購入金額が $XM$ 円だからです。

これらをまとめると、次の条件が必要であることがわかります（逆に、この条件を満たせば、 $x_{i}, y_{i}$ はともに 0 以上 $A_{i}$ 以下の値になります）。

【 $P$ が満たすべき条件　その 1】
$XM \le P \le Ym$

次に、大きい飴の個数 $y_{i} = \displaystyle \frac{P - X A_{i}}{Y - X}$ が整数となる条件を考えます。なお、大きい飴の個数が整数であれば、小さい飴と大きい飴の個数の総和が整数（ $A_{i}$ です）であることから、小さい飴の個数も整数になります。したがって、大きい飴の個数が整数になる条件を考えれば十分です。

$y_{i} = \displaystyle \frac{P - X A_{i}}{Y - X}$ が整数であるということは、 $P - X A_{i}$ が $Y - X$ で割り切れるということです。

つまり、 $D = Y - X$ とおくと、 $P - X A_{1}, P - X A_{2}, \dots, P - X A_{N}$ がすべて $D$ の倍数であるということです。このことを合同式でかくと、次のようになります（なお、合同式に馴染みのない方は、『チャート式数学A』などで復習してみてください）。

$P \equiv X A_{1} \pmod D$
$P \equiv X A_{2} \pmod D$
......
$P \equiv X A_{N} \pmod D$

よって、

$X A_{1} \equiv X A_{2} \equiv \dots \equiv X A_{N} \pmod D$

が成り立ちます。つまり、 $X A_{1}, X A_{2}, \dots, X A_{N}$ を $D$ で割った余りがすべて等しくなければならないということです。さらに、 $P$ で割った余りも、それと一致する必要があります。

【 $P$ が満たすべき条件　その 2】

$X A_{1}, X A_{2}, \dots, X A_{N}$ を $D$ で割った余りを $r$ とすると、

$P$ を $D$ で割った余りも $r$ である

以上の「条件その 1・条件その 2」を満たせば、人 $i$ が小さい飴を買った個数 $x_{i}$ 、大きい飴を買った個数 $y_{i}$ は、ともに $0$ 以上 $A_{i}$ 以下の整数になります。

トドメ

最後に、「大きい飴」の購入個数の総和が最大になるような $P$ の決め方を考えましょう。これは、実は簡単です。

大きい飴の方が、小さい飴よりも単価が高いのですから、合計購入個数が同じならば、購入金額が高ければ高いほど、大きい飴の購入個数は大きくなります。実際、大きい飴の購入個数 $y_{i}$ についての式

$\displaystyle y_{i} = \frac{P - X A_{i}}{Y - X}$

を見ると、 $P$ が大きくなればなるほど、 $y_{i}$ も大きくなることが分かります。

以上をまとめると、この問題の解法は次のように整理できます。

最終的な解法

まず、 $X A_{1}, X A_{2}, \dots, X A_{N}$ を $D$ で割った余りがすべて等しいという条件を満たさない場合は、-1 を出力する。

このとき、 $D$ で割った余りが $r$ である $Ym$ 以下の最大の整数を $P$ とすればよい。

ただし、この $P$ が $XM$ 未満となるならば、条件を満たす $P$ は存在しないので、-1 を出力する。

ㅤ

補足：D で割った余りが r である Ym 以下の最大の整数の求め方

一般に「 $q$ で割った余りが $r$ である $L$ 以下の最大の整数」は次のコードのように求められます。

// a を b で割ったときの商（a が負の場合にも対応できるもの）
long long floor(long long a, long long b) {
    if (a % b == 0 || a >= 0) return a / b;
    else return -((-a) / b) - 1;
}

// q で割った余りが r である、L 以下の最大の整数を求める
long long max_qr(long long q, long long r, long long L) {
    // L - r 以下の最大の q の倍数を求めて、それに r を足したものを求めればよい
    // L - r 以下の最大の q の倍数は、q * floor(L - r, q) である
    return q * floor(L - r, q) + r;
}

AC コード

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


// a を b で割ったときの商（a が負の場合にも対応できるもの）
long long floor(long long a, long long b) {
    if (a % b == 0 || a >= 0) return a / b;
    else return -((-a) / b) - 1;
}

int main() {
    long long N, X, Y;
    cin >> N >> X >> Y;
    vector<long long> A(N);
    for (int i = 0; i < N; i++) cin >> A[i];

    // M: A の最大値、m: A の最小値
    long long M = A[0], m = A[0], D = Y - X;
    for (int i = 0; i < N; i++) {
        M = max(M, A[i]);
        m = min(m, A[i]);
    }

    // X A[0], X A[1], ... を D で割った余りはすべて等しくなければならない
    long long r = X * A[0] % D;
    for (int i = 0; i < N; i++) {
        if (X * A[i] % D != r) {
            cout << -1 << endl;
            return 0;
        }
    }

    // Ym 以下の、D で割った余りが r である整数のうち、最大のものを P とする
    long long P = D * floor(Y * m - r, D) + r;

    // P が XM 未満はダメ
    if (P < X * M) {
        cout << -1 << endl;
        return 0;
    }

    // 最終結果を求める
    long long res = 0;
    for (int i = 0; i < N; i++) {
        long long yi = (P - X * A[i]) / D;
        res += yi;
    }
    cout << res << endl;
}

けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

AtCoder ABC 432 C - Candy Tribulation (1Q, 茶色, 350 点)

問題概要（一部意訳）

制約

考えたこと

購入金額を決め打ったときの、各人の購入金額

購入価格 $P$ が満たすべき条件

トドメ

最終的な解法

AC コード

問題概要（一部意訳）

制約

考えたこと

購入金額を決め打ったときの、各人の購入金額

購入価格 が満たすべき条件

トドメ

最終的な解法

AC コード

購入価格 $P$ が満たすべき条件