概要

\(N\) 人のメンバーに \(M\) 種類のお菓子からちょうど \(K\) 個ずつ（すべて異なる種類で）配れるかを判定する問題です。各種類のお菓子の個数制限を守りつつ全員に配れるかどうかを、シンプルな条件式で判定できます。

考察

問題のモデル化

この問題を整理すると、次のような割り当て問題になります：

• \(N\) 人のメンバーそれぞれに、\(M\) 種類の中から \(K\) 種類を選んで1個ずつ渡す
• 種類 \(i\) のお菓子は合計で \(C_i\) 個しかないので、最大 \(C_i\) 人にしか配れない

これは二部グラフのマッチング（フロー問題）として捉えることができます。左側に \(N\) 人のメンバー、右側に \(M\) 種類のお菓子を置き、各メンバーから全種類に辺を張ります。メンバー側の各ノードは次数ちょうど \(K\)、種類 \(i\) のノードは次数最大 \(C_i\) という条件です。

重要な気づき：対称性

すべてのメンバーは「全 \(M\) 種類のお菓子と接続している」という意味で完全に対称です。つまり、どのメンバーも同じ選択肢を持っています。

このような対称な構造では、ボトルネックになるのは全体としてお菓子が足りるかどうかだけです。具体的には：

• 種類 \(i\) のお菓子は \(C_i\) 個ありますが、各メンバーには1個しか渡せないので、\(N\) 人に対して種類 \(i\) が貢献できるのは \(\min(C_i, N)\) 人分です。
• 全種類を合わせた貢献の合計 \(\sum_{i=1}^{M} \min(C_i, N)\) が、必要な総配布数 \(N \times K\) 以上であれば配布可能です。

なぜこれで十分か

フロー理論の最大フロー最小カット定理から説明できます。ソースから各メンバーへ容量 \(K\) の辺、各メンバーから全種類へ容量 \(1\) の辺、各種類からシンクへ容量 \(C_i\) の辺を張ります。

メンバー側が完全に対称なので、最小カットを考えると、制約が最もきつくなるのはメンバー全員を含む場合です。このとき、シンク側の容量は \(\sum \min(C_i, N)\) となり、これが \(N \times K\) 以上なら最大フローが \(N \times K\) に達します。

具体例

\(N=3, M=3, K=2, C=[2, 3, 1]\) の場合：

• \(\min(2,3) + \min(3,3) + \min(1,3) = 2 + 3 + 1 = 6\)
• \(N \times K = 3 \times 2 = 6\)
• \(6 \geq 6\) なので Yes

アルゴリズム

1. 各 \(C_i\) について \(\min(C_i, N)\) を計算し、その総和を求める
2. 総和が \(N \times K\) 以上なら Yes、そうでなければ No を出力

計算量

• 時間計算量: \(O(M)\)（各種類について \(\min(C_i, N)\) を計算して合計するだけ）
• 空間計算量: \(O(M)\)（入力の格納）

実装のポイント

• \(N\) と \(K\) がともに最大 \(10^9\) になりうるため、\(N \times K\) は \(10^{18}\) に達します。Python では多倍長整数が標準なのでオーバーフローの心配はありませんが、C++ などでは long long を使う必要があります。

• \(\min(C_i, N)\) の計算を忘れると、1人に同じ種類を2個以上渡すことに相当する不正な計算になってしまうので注意が必要です。

  ソースコード

import sys

def solve():
    input_data = sys.stdin.read().split()
    N = int(input_data[0])
    M = int(input_data[1])
    K = int(input_data[2])
    C = [int(input_data[3 + i]) for i in range(M)]
    
    # Each member gets exactly K candies, all different types.
    # Each type i can be given to at most C_i members (and at most 1 per member).
    # We need to assign to N members, K types each, such that type i is used at most C_i times.
    
    # This is equivalent to: does there exist a bipartite graph between N members and M types,
    # where each member has degree exactly K, and each type i has degree at most C_i?
    
    # By Hall's theorem / deficiency version, this is possible if and only if:
    # sum(min(C_i, N)) >= N * K
    # 
    # But we also need K <= M (given by constraints).
    # 
    # Actually, let me think more carefully. We need to check if a bipartite graph exists
    # where one side has N nodes each with degree K, and the other side has M nodes where
    # node i has degree at most C_i.
    #
    # By the Gale-Ryser theorem (or flow arguments), the necessary and sufficient condition is:
    # 1) sum(min(C_i, N)) >= N * K
    # 2) K <= M
    #
    # Condition 2 is guaranteed by constraints.
    #
    # Let me verify condition 1 is sufficient. We can think of it as a flow problem:
    # source -> each member with capacity K, each member -> each type with capacity 1,
    # each type -> sink with capacity C_i. Max flow = N*K iff sum(min(C_i, N)) >= N*K.
    # 
    # Actually, for the max flow to be N*K, we need:
    # - For every subset S of members, the neighborhood capacity is enough.
    # By symmetry (all members are identical in terms of connectivity - each connects to all M types),
    # the binding constraint is the full set: sum(min(C_i, N)) >= N*K.
    # Also each member can get at most M types, so K <= M is needed.
    
    total = 0
    for i in range(M):
        total += min(C[i], N)
    
    if total >= N * K:
        print("Yes")
    else:
        print("No")

solve()

---

この解説は claude4.6opus-thinking によって生成されました。