概要

各種類のお菓子は「同じメンバーに2個以上渡せない」ため、種類ごとに配れる上限を考えて、全員に合計 \(N \times K\) 個配れるかを判定する問題です。

考察

重要なのは 「種類 \(i\) のお菓子は最大でも \(N\) 個までしか配れない」 という点です。

• たとえ \(C_i\) がとても大きくても、同じ種類を同じ人に2個渡せないので
  種類 \(i\) は「最大でも \(N\) 人に1個ずつ」しか配れません。
• よって、種類 \(i\) から実際に配布に使える個数は
  $\( \min(C_i,\,N) \)$ です。

全員に配るには合計で \(N\) 人 × \(K\) 個、つまり $\( \text{need} = N \times K \)$ 個が必要です。

一方、配布に使える総数は $\( \text{supply} = \sum_{i=1}^{M} \min(C_i,\,N) \)$ です。

• \(\text{supply} < \text{need}\) なら、どう頑張っても総数が足りないので不可能。
• \(\text{supply} \ge \text{need}\) なら可能です。なぜなら、各種類は任意のメンバーに配ってよく制約は「同一種類は同一メンバーに1回まで」だけなので、種類ごとに最大 \(N\) 人へ配れる“枠”の合計が \(N K\) 以上あれば、全員の \(K\) 個分の枠を埋められるためです。

素朴に「誰に何を配るか」をシミュレーションすると、\(N\) が最大 \(10^9\) なので配列すら持てず不可能（TLE/メモリ不足）です。必要なのは 総数の判定 だけです。

具体例： - \(N=3, K=2\)（合計6個必要） - \(C=[10,1,1]\) - \(\min(C_i,N)=[3,1,1]\) なので \(\text{supply}=5\)、足りない → No

アルゴリズム

1. 必要個数 \(\text{need} = N \times K\) を計算する。
2. 各種類 \(i\) について \(\min(C_i, N)\) を足し上げ、\(\text{supply}\) を求める。
3. \(\text{supply} \ge \text{need}\) なら Yes、そうでなければ No。

（提示コードでは、途中で \(\text{supply} \ge \text{need}\) になった時点で早期終了しています。）

計算量

• 時間計算量: \(O(M)\)
• 空間計算量: \(O(1)\)（入力配列以外は定数量）

実装のポイント

• 種類ごとの寄与は必ず \(\min(C_i, N)\) にする（\(C_i\) が \(N\) を超えても使えるのは \(N\) 個まで）。

• \(\text{need}=N\times K\) は値が大きくなり得るので（他言語では特に）64bit整数に注意。Python なら整数は自動で多倍長ですが、早期終了するとより高速です。

  ソースコード

import sys

def main():
    data = list(map(int, sys.stdin.buffer.read().split()))
    if not data:
        return
    N, M, K = data[0], data[1], data[2]
    C = data[3:3 + M]

    need = N * K
    supply = 0
    for ci in C:
        supply += ci if ci < N else N
        if supply >= need:
            print("Yes")
            return
    print("No")

if __name__ == "__main__":
    main()

この解説は gpt-5.2-high によって生成されました。