概要

\(N\) 人のメンバーに、それぞれ異なる種類のお菓子を \(K\) 個ずつ配ることができるかを判定する問題です。お菓子の在庫数と「1人に同じ種類を2個以上配れない」という制約をどう処理するかが鍵となります。

考察

1. 必要な合計個数

まず、全員が \(K\) 個ずつお菓子を受け取るためには、全体で合計 \(N \times K\) 個のお菓子が必要になります。しかし、単に合計個数が足りていれば良いわけではありません。

2. 各種類のお菓子の「有効な上限」

この問題の最も重要な制約は、「同じ種類のお菓子を同じメンバーに 2 個以上配ってはならない」という点です。 メンバーは \(N\) 人しかいないため、ある特定の種類のお菓子 \(i\) がどれだけ大量にあっても（例：\(C_i = 10^{12}\) 個）、その種類のお菓子を配れる人数は最大で \(N\) 人までです。

つまり、種類 \(i\) のお菓子について、実際に配ることができる個数は次のようになります： - 在庫 \(C_i\) が人数 \(N\) 以下のとき：在庫のすべて（\(C_i\) 個）を配ることができる。 - 在庫 \(C_i\) が人数 \(N\) より多いとき：\(N\) 人に 1 個ずつ配るのが限界なので、\(N\) 個までしか配ることができない。

これをまとめると、種類 \(i\) のお菓子が全体の配布に寄与できる最大個数は \(\min(N, C_i)\) となります。

3. 判定条件

すべてのお菓子の種類について、この「有効な個数」を合計したものが、必要な総数 \(N \times K\) 以上であれば、すべての人に \(K\) 個ずつ配ることが可能です。

\[ \sum_{i=1}^{M} \min(N, C_i) \geq N \times K \]

この条件が成り立つとき Yes、そうでなければ No となります。 ※この条件で十分であることは、例えば「在庫が多い順に並べて、各メンバーに順番に割り当てる」といった構成方法を考えることで証明できます。

アルゴリズム

1. 必要な総数 \(Target = N \times K\) を計算する。
2. 各種類のお菓子の個数 \(C_i\) について、\(\min(N, C_i)\) を計算し、その総和 \(Total\) を求める。
3. \(Total \geq Target\) であれば Yes を、そうでなければ No を出力する。

計算量

• 時間計算量: \(O(M)\) お菓子の種類数 \(M\) に対して、1 回のループで各 \(C_i\) を確認するためです。\(N\) や \(C_i\) の値自体は大きくても計算量には影響しません。
• 空間計算量: \(O(M)\) 入力されたお菓子の個数 \(C_1, \ldots, C_M\) をリストに格納するために必要なメモリ量です。

実装のポイント

• 大きな値の扱い: \(N\) や \(C_i\) が最大 \(10^9\) であり、その積である \(N \times K\) は最大 \(10^{14}\) 程度になります。Python では自動的に多倍長整数として扱われますが、他の言語（C++ など）を使用する場合は long long 型などの 64 ビット整数を使用する必要があります。

• 早期終了: 合計を計算している途中で \(N \times K\) を超えた場合にループを抜けるようにすると、わずかですが効率的になります（ただし、最悪計算量は \(O(M)\) で変わりません）。

  ソースコード

import sys

def solve():
    # 入力を取得
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    N = int(input_data[0])
    M = int(input_data[1])
    K = int(input_data[2])
    C = list(map(int, input_data[3:]))
    
    # 判定条件: 各種類のお菓子は最大 N 人にしか配れないため、
    # i 番目のお菓子が寄与できる最大数は min(N, C_i) となる。
    # すべてのメンバーに K 個ずつ配るためには、合計で N * K 個必要。
    # したがって、 sum(min(N, C_i)) >= N * K であれば可能。
    
    total_capacity = 0
    for count in C:
        if count < N:
            total_capacity += count
        else:
            total_capacity += N
            
    if total_capacity >= N * K:
        print("Yes")
    else:
        print("No")

if __name__ == "__main__":
    solve()

この解説は gemini-3-flash-thinking によって生成されました。