概要

\(N\) 人のメンバーに、\(M\) 種類のお菓子からそれぞれ最大1個ずつ選んで、1人あたりちょうど \(K\) 個を配ることが可能かを判定する問題。

考察

この問題では、各メンバーに \(K\) 個のお菓子を配る必要があります。ただし、同じ種類のお菓子を1人には最大1個しか渡せず、また各種類のお菓子には上限 \(C_i\) があります。

素朴な考え

例えば、メンバーごとに使えるお菓子の組み合わせを探索したり、フロー-basedなグラフアルゴリズムを適用することも考えられますが、制約が非常に大きい（\(N\) が最大 \(10^9\)）ため、そういったアプローチでは時間内に解くことはできません。

鍵となる観察

重要なのは「お菓子の種類ごとに、最大何人に配れるか」を考えることです。
\(i\) 番目のお菓子は \(C_i\) 個あり、1人につき最大1個しか渡せないので、「最大 \(\min(C_i, N)\) 人に配れる」と考えられます。
これは、人数 \(N\) が少なければお菓子が余る可能性があり、逆にお菓子が少なければ人数分には配れない、という直感的な上限です。

さらに、全体で必要なのは \(N \times K\) 個のお菓子（1人 \(K\) 個 × \(N\) 人）です。
そのため、各お菓子の「配れる人数の上限」を足し合わせた値が、\(N \times K\) 以上になれば条件を満たせます。

解法の正当性

この貪欲なアプローチが成立するのは、どのお菓子も1人につき最大1個しか使えないという制約があるため、お菓子の種類ごとに独立して扱えるからです。
また、お菓子が多い順に考えることで、できるだけ多くの人に配れる可能性を広げることができます。

アルゴリズム

1. 各お菓子の個数 \(C_i\) を降順にソートします（実はソートしなくても解けますが、直感的にわかりやすいため）。
2. 各お菓子 \(i\) について、最大で \(\min(C_i, N)\) 人に配れると考え、合計を加算していきます。
3. 合計が \(N \times K\) に達したら Yes を出力し終了。すべて見終わっても足りなければ No。

計算量

• 時間計算量: \(O(M)\)
• 空間計算量: \(O(1)\) （入力を除く）

※ソートを行う場合、時間計算量は \(O(M \log M)\) になりますが、実際には必要ありません。

実装のポイント

• 各お菓子の配れる上限は \(\min(C_i, N)\) であること。
• 合計が \(N \times K\) を超えた時点で早期終了できるので、大きな入力でも高速に動作します。
• Python では input() の代わりに sys.stdin.read() を使うことで、大量の入力を高速に読み込めます。

## ソースコード

```python
import sys
import heapq

def main():
    import sys
    input = sys.stdin.read
    data = input().split()
    
    N = int(data[0])
    M = int(data[1])
    K = int(data[2])
    
    C = list(map(int, data[3:3+M]))
    
    # 各お菓子の個数を降順にソートする
    C.sort(reverse=True)
    
    # 最大ヒープを用意する（Pythonでは最小ヒープなので負にして使う）
    # 各メンバーが持てる残りの必要なお菓子の数を管理する
    # 初期状態では、各メンバーがK個持つ必要がある
    # しかし、N人がそれぞれK個必要なので、合計 N*K 個が必要
    # それぞれの種類のお菓子を最大何人に配れるかを考える
    
    # 貪欲法：多い順にお菓子を見て、各お菓子を最大限配る
    # 各お菓子 i は C[i] 個あるので、最大 C[i] 人に配れる（1人1個まで）
    # 全体で N 人の人に K 個ずつ配る必要がある → 合計 N*K 個必要
    
    # 各お菓子を最大 min(C[i], N) 人に配ることができる（1人につき1個まで）
    # しかし、より正確には、今持っている最も需要の高い（残り少ない）人に優先的に配るべき
    
    # より効率的な方法：
    # 各お菓子 i について、最大 min(C[i], N) 人に配れる
    # つまり、合計で sum(min(C[i], N) for i in range(M)) 個配れる
    # これが N*K 以上であれば OK
    
    total = 0
    for c in C:
        total += min(c, N)
        if total >= N * K:
            print("Yes")
            return
    print("No")

if __name__ == "__main__":
    main()

---

この解説は qwen3-coder-480b によって生成されました。