概要

この問題は、各届け先ごとの割り当てを細かく考える必要はなく、荷物の総数と全ドライバーが運べる総容量を比べるだけで判定できます。
すべての荷物の合計が \(N \times K\) 以下なら配送可能、そうでなければ不可能です。

考察

一見すると、

• どのドライバーがどの届け先を担当するか
• 1つの届け先を複数人でどう分担するか

を考えないといけないように見えます。
しかし、この問題にはとても重要な条件があります。

• 1人のドライバーは複数の届け先を担当してよい
• 1つの届け先の荷物は複数のドライバーで分担してよい
• 荷物は整数個単位で割り当てればよい

つまり、届け先ごとの境界はほとんど意味がありません。
荷物全体を「ただの荷物の集まり」とみなしてしまってよいです。

重要な気づき

各ドライバーは最大 \(K\) 個まで運べるので、\(N\) 人全体では最大で

\(N \times K\)

個の荷物を運べます。

一方、運ばなければならない荷物の総数は

\(\displaystyle \sum_{i=1}^{M} A_i\)

です。

したがって、

• \(\sum A_i \leq N \times K\) なら配送可能
• \(\sum A_i > N \times K\) なら配送不可能

となります。

なぜこれだけでよいのか

例えば、ある届け先の荷物数 \(A_i\) が \(K\) より大きくても問題ありません。
その届け先の荷物は複数人で分担できるからです。

逆に、各ドライバーが複数の届け先をまたいで荷物を持てるので、細かい組み合わせを考えなくても、総容量さえ足りていれば必ず割り当てられます。

具体例

例えば、

• \(N = 3\)
• \(K = 5\)

なら、全体で運べる荷物は \(3 \times 5 = 15\) 個です。

届け先の荷物が

• \(A = [4, 7, 3]\)

なら、合計は \(4 + 7 + 3 = 14\) 個なので配送可能です。

実際には例えば次のように分けられます。

• ドライバー1: 5個
• ドライバー2: 5個
• ドライバー3: 4個

どの届け先の荷物を誰が何個持つかは自由なので、合計容量が足りていれば問題ありません。

素朴なアプローチが不要な理由

「各届け先をどう割り当てるか」をシミュレーションしたり、貪欲法やDPを考えたりしたくなるかもしれません。
しかしこの問題では分割の自由度が非常に高いため、そのような複雑な処理は不要です。

必要なのは、\(M\) 個の \(A_i\) をすべて足して、\(N \times K\) と比較するだけです。

アルゴリズム

1. \(A_i\) の総和 total を求める
2. total <= N * K なら Yes
3. そうでなければ No

計算量

• 時間計算量: \(O(M)\)
• 空間計算量: \(O(1)\)

実装のポイント

• \(A_i\) の総和は最大で \(10^5 \times 10^9 = 10^{14}\) になるため、言語によっては 64bit整数 が必要です。

• Python では整数の桁数を気にしなくてよいので、そのまま合計して問題ありません。

• 入力は \(A_i\) が \(M\) 行にわたって与えられるため、順に読みながら合計するだけで十分です。

  ソースコード

import sys

def main():
    input = sys.stdin.readline
    N, M, K = map(int, input().split())
    total = 0
    for _ in range(M):
        total += int(input())
    print("Yes" if total <= N * K else "No")

if __name__ == "__main__":
    main()

---

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