AtCodeで緑コーダーを目指して、精進中ですが、
2025年11月15日の問題が少し難しかったのでまとめておきます！
https://atcoder.jp/contests/abc432/tasks/abc432_c
まずは、C問題を安定して解けるレベルを目指したいですね〜
導入：飴を配るだけなのに、なぜこんなに難しい？
この記事では、AtCoder の「小さな飴と大きな飴」のような、
全員に配る飴の個数は決まっているが、
総重量を揃えつつ大きな飴の総数を最大化したい、 というタイプの問題を解説します。
問題文は読めるけれど、
- X と Y が出てくると難しく感じる
- Ai 個配ると言われると数式に落とすのが難しい
- 「全員の総重量が同じ」という条件を式にするのが苦手
という初級〜中級者向けに、「問題文 → 数式 → 条件整理 → 実装」という流れを丁寧に追っていきます。 キーワードは次の3つです。
- 総重量
- 重さの差（Y−X）
- 大きな飴の最大個数
問題の要点整理：何を満たせば良いのか？
問題設定のポイントをまとめると次の通りです。
- 小さな飴の重さは X グラム
- 大きな飴の重さは Y グラム（X < Y）
- 子供 i には Ai 個の飴を配る（小＋大の合計）
- 全員の総重量を等しくしたい
- さらに大きな飴の総数を最大化したい
ここから、小さな飴の数を s_i、大きな飴の数を l_i として数式化していきます。
数式化してみよう：X と Y と Ai の関係を式にする
子供 i について、小さな飴と大きな飴の個数を以下で表します。
- s_i：小さい飴の数
- l_i：大きい飴の数
合計個数の条件は s_i + l_i = Ai。 総重量は X × s_i + Y × l_i。
全員の総重量を W とすると、
W = X × s_i + Y × l_i
ここで s_i = Ai – l_i を代入すると、
W = X × Ai + (Y – X) × l_i
この式から「大きな飴を1つ増やすと総重量が (Y – X) 増える」ことがわかります。
可能条件の導出1：全員の総重量を揃えられるか？
総重量 W を比較すると、 X × A1 + D × l1 = X × Ai + D × li が必要になります（D = Y – X）。
この式から導かれる結論は次の通りです。
差分 (A1 – Ai) が D と X の最大公約数を使った特定の周期で一致していないと、 どんな配り方でも W を揃えることはできません。
判定手順は以下です。
- D = Y – X を求める
- g = gcd(D, X) を求める
- mod = D / g を求める
- (Ai – A1) が mod の倍数かチェックする
1つでも外れると解なし（-1）となります。
可能条件の導出2：総重量 W の範囲
l_i の最小値と最大値から、 各子供の総重量は次の範囲に入ります。
- 最低重量：X × Ai（全部小さい飴）
- 最高重量：Y × Ai（全部大きい飴）
よって W は全員の範囲を満たす必要があり、
max(X × Ai) ≤ W ≤ min(Y × Ai)
が条件となります。範囲が重ならなければ解なしです。
大きな飴の総数を最大化する考え方
l_i = (W – X × Ai) / D より、大きな飴の総数 L は W に対して単調増加します。
つまり、許される W の中で最大の W を使えば良い、ということです。
実装方針
1. 前処理
- D、g、mod を求める
- すべての Ai について (Ai – A1) の mod 判定を行う
2. W の範囲決定
W_low = max(X × Ai)
W_high = min(Y × Ai)
W_low > W_high の場合は即 -1。
3. W の探索
W は一定周期（D の倍数）でしか取り得ないため、 最大になるように調整しながら探します。
4. 整数性の確認
求めた W で各 l_i が整数かつ 0 〜 Ai の範囲かチェックします。
5. 大きい飴の総数を計算
すべて問題なければ L = Σ (W – X × Ai) / D を出力します。
実装例（ケビン作成、Typescript）
NumberだとWAが出るので、BigIntにしてます。
import * as fs from "fs";
const gcdBigInt = (a: bigint, b: bigint): bigint => {
a = a < 0n ? -a : a;
b = b < 0n ? -b : b;
while (b !== 0n) {
const t = a % b;
a = b;
b = t;
}
return a;
};
const modBigInt = (a: bigint, m: bigint): bigint => {
const r = a % m;
return r < 0n ? r + m : r;
};
function main(input: string): void {
const trimmedInput = input.trim();
const [rawNXY, rawAs] = trimmedInput.split(/\r?\n/);
const [N, rawX, rawY] = rawNXY.split(" ").map(Number);
const X = BigInt(rawX);
const Y = BigInt(rawY);
const As = rawAs.split(" ").map(BigInt);
const D = Y - X;
const g = gcdBigInt(D, X);
const M = D / g;
const A0 = As[0];
for (let i = 1; i < As.length; i++) {
if (modBigInt(As[i] - A0, M) !== 0n) {
console.log(-1);
return;
}
}
let L = X * As[0];
let R = Y * As[0];
for (let i = 0; i < As.length; i++) {
const Ai = As[i];
const minW = X * Ai;
const maxW = Y * Ai;
if (minW > L) L = minW;
if (maxW < R) R = maxW;
}
if (L > R) {
console.log(-1);
return;
}
const k = modBigInt(X*A0, D);
const rem = modBigInt(R - k , D);
const W = R - rem;
let total = 0n;
for (let i = 0; i < N; i++) {
const Ai = As[i];
const numerator = W - X * Ai;
const bi = numerator / D;
total += bi;
}
console.log(total.toString());
}
const inputData: string = fs.readFileSync("/dev/stdin", "utf8")
main(inputData);
まとめ：数式化で「重さの差」を味方にする
今回の問題のポイントは以下です。
- 総重量は X × Ai + (Y – X) × li の形で書ける
- 重さの差 D = Y – X が最重要
- Ai の周期性チェックで「解が存在するか」が決まる
- W の範囲条件と周期性を使うと実装が可能
- 大きな飴の総数は W の最大値で決まる
数式化を通じて問題全体がシンプルになり、
「X、Y、Ai の関係をどう扱うか」が見えてきます。
皆様の参考になれば幸いです！
