概要

修学旅行の班長が \(N\) 人のメンバーに \(K\) 個ずつお菓子を配る際、購入した \(M\) 種類のお菓子の在庫制約下で配布が可能か判定する問題です。

考察

素朴なアプローチでは、お菓子の総数が \(N \times K\) 以上必要ですが、それだけでは不十分です。重要な観察は、同じ種類のお菓子を同じメンバーに2個以上配れないという制約です。つまり、各お菓子の種類は最大でも \(N\) 人にしか配れませんが、さらに制約を深く考える必要があります。

具体的には、各メンバーは \(K\) 種類の異なるお菓子を受け取るため、あるお菓子の種類が多くても \(N\) 個までしか活用できません。しかし、\(K\) 種類以上のお菓子がある場合、各メンバーが受け取る \(K\) 個のお菓子は異なる種類であるため、同じ種類のお菓子を複数のメンバーに配布する際の上限は \(N\) ですが、それ以外の制約も生じます。

特に、各メンバーは \(K\) 個のお菓子を受け取るため、\(K\) 種類のお菓子についてはそれぞれ最大 \(N\) 個まで配布できますが、\(K\) 種類を超えるお菓子については、各メンバーが既に \(K\) 個受け取っているため、それ以上は配布できません（つまり、最大 \(N-1\) 個までしか配布できません）。この制約を考慮して、在庫を効率的に配布できるかどうかを判定する必要があります。

アルゴリズム

1. まず、お菓子の総数が \(N \times K\) 以上あるかチェックします。不足している場合は明らかに “No” です。
2. 次に、お菓子の種類を個数の降順にソートします。
3. ソートしたお菓子のリストについて、上位 \(K\) 種類については最大 \(N\) 個まで、それ以降の種類については最大 \(N-1\) 個まで配布できると仮定して、合計で配布可能な個数を計算します。
4. この合計が \(N \times K\) 以上であれば “Yes”、そうでなければ “No” を出力します。

このアプローチは、各メンバーが \(K\) 個のお菓子を受け取る際に、最も多いお菓子から優先的に \(N\) 個まで配布し、残りのお菓子は \(N-1\) 個までしか配布できないという制約を効率的に表現しています。

計算量

• 時間計算量: \(O(M \log M)\)（お菓子の種類のソートが支配的）
• 空間計算量: \(O(M)\)（お菓子のリストの保持）

実装のポイント

• 入力値が大きいため、全体の和を取る際はオーバーフローに注意（Pythonでは整数オーバーフローは起きないが、他の言語では注意）。

• お菓子のリストを降順にソートし、上位 \(K\) 種類とそれ以外で処理を分けることが重要です。

• 各お菓子の種類について、配布可能な上限を min(C[i], N) や min(C[i], N-1) で計算することで、在庫過多の場合を適切に処理します。

  ソースコード

import sys

def main():
    data = sys.stdin.read().split()
    if not data:
        print("No")
        return
        
    N = int(data[0])
    M = int(data[1])
    K = int(data[2])
    C = list(map(int, data[3:3+M]))
    
    total_needed = N * K
    
    if sum(C) < total_needed:
        print("No")
        return
        
    max_per_kind = N
    C.sort(reverse=True)
    
    total_available = 0
    for i in range(M):
        if i < K:
            total_available += min(C[i], N)
        else:
            total_available += min(C[i], N - 1)
            
    if total_available >= total_needed:
        print("Yes")
    else:
        print("No")

if __name__ == "__main__":
    main()

この解説は deepseekv3 によって生成されました。