概要

\(N\) 人のドライバー（1人あたりの積載制限 \(K\)）が、計 \(M\) 箇所の届け先にある合計 \(\sum A_i\) 個の荷物をすべて運びきれるかどうかを判定する問題です。

考察

この問題の重要な点は、「荷物を1個単位で自由に分割してドライバーに割り当てられる」というルールです。

具体的には以下の条件が認められています： - 同じ届け先の荷物を、複数のドライバーで分担して運ぶことができる。 - 1人のドライバーが、異なる届け先の荷物を組み合わせて運ぶことができる。

もし「荷物を分割できない（1つの届け先の荷物は必ず1人が運ぶ）」という条件であれば、これは「ビンパッキング問題」と呼ばれる非常に難しい問題になります。しかし、本問では荷物をバラバラにして運ぶことができるため、複雑な組み合わせを考える必要はありません。

ドライバー全員が運べる荷物の総容量は \(N \times K\) 個です。一方で、運ぶ必要がある荷物の総数は \(A_1 + A_2 + \dots + A_M\) 個です。 荷物を自由に分配できる以上、「荷物の総数がドライバー全員の総容量以下であること」が、すべての荷物を配送できるための必要十分条件となります。

アルゴリズム

1. 荷物の総数 \(S = \sum_{i=1}^{M} A_i\) を計算します。
2. ドライバーの総容量 \(C = N \times K\) を計算します。
3. \(S \le C\) であれば Yes を、そうでなければ No を出力します。

計算量

• 時間計算量: \(O(M)\)
  • 荷物の個数 \(A_i\) の総和を求めるために、リストを1回走査する必要があります。
• 空間計算量: \(O(M)\)
  • 入力された \(M\) 個の荷物データを保持するためにメモリを使用します。

実装のポイント

• 大きな数値の扱い: \(N, K, A_i\) は最大で \(10^9\) であり、それらの総和や積は \(10^{18}\) 程度に達します。Pythonは標準で多倍長整数（大きな整数）を扱えるため、オーバーフローを気にせず計算できます。

• 高速な入力: \(M\) が最大 \(10^5\) と比較的大きいため、sys.stdin.read().split() などを用いて入力を一括で取得することで、実行時間を短縮できます。

  ソースコード

import sys

def solve():
    # Read all input at once and split it into tokens based on whitespace.
    # This is efficient for the given constraints (M up to 10^5).
    input_data = sys.stdin.read().split()
    
    # Check if we have at least the initial parameters N, M, and K.
    if len(input_data) < 3:
        return
    
    # N: Number of drivers
    # M: Number of destinations
    # K: Maximum number of items each driver can carry
    n = int(input_data[0])
    m = int(input_data[1])
    k = int(input_data[2])
    
    # Each destination i requires A_i items.
    # The problem states that items for the same destination can be split
    # among multiple drivers and that each driver can carry items for
    # multiple destinations. The only constraint is that each driver
    # can carry at most K items in total, and items are discrete units.
    
    # Calculate the total number of items to be delivered by summing all A_i.
    # The A_i values are the remaining tokens from index 3 to 3+m-1.
    # Python's sum and map functions are optimized for this kind of operation.
    total_items = sum(map(int, input_data[3:3+m]))
    
    # Calculate the total capacity of all N drivers combined.
    # Python handles large integers (up to 10^18 in this case) automatically.
    total_capacity = n * k
    
    # Since any item can be assigned to any driver as long as their capacity 
    # of K is not exceeded, the condition for success is simply that the 
    # total number of items does not exceed the total combined capacity.
    if total_items <= total_capacity:
        print("Yes")
    else:
        print("No")

if __name__ == '__main__':
    solve()

この解説は gemini-3-flash-thinking によって生成されました。