概要

\(N\) 人のドライバー（各自最大 \(K\) 個運搬可能）で、\(M\) 件の届け先の荷物をすべて届けられるかを判定する問題です。同じ届け先の荷物を複数ドライバーで分担できるため、荷物の総数と総容量の比較だけで解けます。

考察

重要な気づき：荷物は自由に分割できる

この問題の最も重要なポイントは、同じ届け先の荷物を複数のドライバーで分担できるという条件です。

例えば、\(K = 5\)（1人最大5個）で、ある届け先に荷物が12個あるとき、ドライバーAに5個、ドライバーBに5個、ドライバーCに2個、と分けて運ぶことができます。

ビンパッキング問題にならない理由

もし「1つの届け先の荷物は1人のドライバーが丸ごと運ばなければならない」という制約があれば、いわゆるビンパッキング問題（NP困難）になりますが、本問ではそのような制約はありません。

荷物は整数個単位で自由に分割してドライバーに割り当てられるため、各ドライバーの容量 \(K\) を隙間なく埋めていくことが可能です。

具体例で確認

• \(N = 3\), \(K = 5\)（総容量 \(15\)）、\(A = [7, 4, 3]\)（総荷物 \(14\)）
  • ドライバー1: 届け先1から5個 → 残り容量0使用で5個
  • ドライバー2: 届け先1から2個 + 届け先2から3個 → 5個
  • ドライバー3: 届け先2から1個 + 届け先3から3個 → 4個
  • 総荷物 \(14 \leq 15\) なので Yes

このように、分割可能であれば隙間なく詰められるため、判定条件は単純に 荷物の総数 ≤ ドライバーの総容量 となります。

判定条件

\[\sum_{i=1}^{M} A_i \leq N \times K\]

が成り立てば Yes、そうでなければ No です。

アルゴリズム

1. \(N\), \(M\), \(K\) を読み込む
2. \(A_1, A_2, \ldots, A_M\) を読み込み、総和 \(\text{total} = \sum A_i\) を計算する
3. \(\text{total} \leq N \times K\) なら Yes、そうでなければ No を出力する

計算量

• 時間計算量: \(O(M)\)（\(A_i\) の総和を求めるだけ）
• 空間計算量: \(O(M)\)（配列 \(A\) の格納。逐次加算すれば \(O(1)\) も可能）

実装のポイント

• \(N\) と \(K\) はそれぞれ最大 \(10^9\) なので、\(N \times K\) は最大 \(10^{18}\) に達します。C++ などでは long long を使う必要がありますが、Python では整数のオーバーフローを気にする必要がありません。

• \(\sum A_i\) も \(M \times \max(A_i) = 10^5 \times 10^9 = 10^{14}\) 程度になりうるため、同様に大きな整数の扱いに注意が必要です（Python では問題なし）。

  ソースコード

import math

def main():
    N, M, K = map(int, input().split())
    A = [int(input()) for _ in range(M)]
    
    # Each A_i requires ceil(A_i / K) drivers at minimum
    # Total drivers needed is sum of ceil(A_i / K)
    # But we can also pack multiple destinations into one driver's capacity
    # 
    # Actually, since items from different destinations can share a driver,
    # the minimum number of drivers needed is:
    # max(ceil(sum(A) / K), max over i of ceil(A_i / K))
    # Wait, no. Since we can split a destination across multiple drivers,
    # the constraint is simply: sum(A) <= N * K
    # But also, each A_i <= N * K (which is implied if sum(A) <= N * K when A_i <= sum(A))
    # Actually no: A_i could be larger than N*K if N*K < A_i.
    # But if sum(A) <= N*K, then A_i <= sum(A) <= N*K, so that's fine.
    # 
    # Hmm wait, let me reconsider. Each driver can carry at most K items total.
    # We have N drivers. Total capacity is N*K.
    # Since items can be freely split (in integer units) across drivers,
    # the only constraint is sum(A) <= N * K.
    # 
    # Actually, is there a bin-packing issue? No, because items from the same
    # destination CAN be split. So each A_i can be divided into chunks that
    # fit into any driver's remaining capacity. This is essentially a 
    # continuous/divisible bin packing problem, so the answer is simply
    # whether sum(A) <= N * K.
    
    total = sum(A)
    if total <= N * K:
        print("Yes")
    else:
        print("No")

main()

---

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