概要

\(M\) 日間にわたって毎日 1 件ずつ発生する合計 \(M\) 件のリクエストを、\(N\) 台のサーバーに割り当てます。各サーバー \(i\) には処理できる回数の上限 \(A_i\) が決まっており、すべてのリクエストを上限を超えないように割り当てられるかを判定する問題です。

考察

この問題を解くための重要なポイントは、「システム全体で最大何回のリクエストを処理できるか」を考えることです。

各サーバーが処理できる回数の上限が \(A_1, A_2, \ldots, A_N\) であるとき、システム全体で受け入れ可能なリクエストの総数は、これらの値をすべて足し合わせた合計値となります。

• リクエストを捌ききれる場合 システム全体の合計処理可能回数が、キャンペーン期間中に発生するリクエストの総数 \(M\) 以上であれば、リクエストを適切に各サーバーへ振り分けることで、どのサーバーもダウンさせずに乗り切ることができます。 （例：リクエストが来るたびに、まだ上限に余裕があるサーバーをどれか 1 つ選んで割り当てればよい）

• リクエストを捌ききれない場合 サーバーの処理可能回数の合計が \(M\) 未満である場合、どのようにリクエストを割り振ったとしても、最終的にはどこかのサーバーで上限を超えてしまうか、あるいはリクエストを処理できなくなります。

したがって、この問題はシンプルに 「\(A_i\) の総和が \(M\) 以上かどうか」 を判定する問題に帰着できます。

アルゴリズム

1. 入力として \(N, M\) および各サーバーの処理可能回数 \(A_i\) を受け取ります。
2. \(A_i\) の総和 \(S = \sum_{i=1}^N A_i\) を計算します。
3. \(S \geq M\) であれば Yes を、そうでなければ No を出力します。

計算量

• 時間計算量: \(O(N)\)
  • サーバーの台数 \(N\) 個の数値を読み込み、その合計を計算するため、 \(N\) に比例した時間がかかります。
• 空間計算量: \(O(N)\)
  • 入力された \(A_i\) をリスト等に保持する場合、 \(N\) に比例したメモリを使用します。

実装のポイント

• 大きな数値の扱い: \(M\) や \(A_i\) の値は最大で \(10^9\) と非常に大きくなりますが、Python 3 では整数の大きさに制限がないため、オーバーフローを気にせずにそのまま合計を計算して比較することができます。
• 入力の高速化: \(N\) が \(10^5\) 程度と大きいため、大量の数値を読み込む必要があります。Python の場合、 input() を何度も呼び出すよりも sys.stdin.read().split() などを使って一括で読み込む方が高速です。

ソースコード

import sys

def solve():
    # 標準入力からNとMを読み込む
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    n = int(input_data[0])
    m = int(input_data[1])
    
    # サーバーの処理可能回数A_iを読み込む
    a = list(map(int, input_data[2:]))
    
    # 全サーバーの処理可能回数の合計を計算する
    total_capacity = sum(a)
    
    # 合計がキャンペーン期間中のリクエスト数M以上であれば、割り当てが可能
    if total_capacity >= m:
        print("Yes")
    else:
        print("No")

if __name__ == "__main__":
    solve()

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