概要

全サーバーの処理可能回数の合計が、キャンペーン日数 \(M\) 以上であれば、すべてのリクエストを処理できるかどうかを判定する問題。

考察

この問題では、毎日1件のリクエストが発生し、それを \(N\) 台のサーバーにうまく振り分けて、どのサーバーも処理可能回数を超えないようにすることが目的です。

重要な観察は、「各サーバーに割り当てたリクエスト数」を個別に考える必要がないということです。なぜなら、最終的に必要なのは 全体の処理可能回数の総和 だけだからです。

例えば、サーバーが3台あって、それぞれの処理可能回数が \(A = [3, 2, 1]\) で、\(M = 5\) の場合、合計処理可能回数は \(3 + 2 + 1 = 6\) なので、5件のリクエストは処理可能です。

逆に、\(M = 7\) なら処理しきれません。

したがって、個々のリクエストをどのサーバーに割り振るかという詳細な割当を考える必要はなく、単純に 総和を求めて比較するだけで判定できます。

素朴なアプローチとして、毎日貪欲に最も余裕のあるサーバーに割り当てていく方法が考えられますが、\(M\) が最大 \(10^9\) まであり得るので、このシミュレーションを行うと時間内に終わりません（TLE）。しかし、実はこの複雑な割当ロジックは不要であり、総和の比較だけで十分です。

アルゴリズム

1. 各サーバーの処理可能回数 \(A_i\) の合計値を求める。
2. その合計値が \(M\) 以上であれば Yes、そうでなければ No を出力する。

計算量

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

※ 合計を求めるのにすべての要素を一度走査する必要があるため、時間計算量は \(O(N)\)。入力の配列を保持するので空間計算量も \(O(N)\)。

実装のポイント

• 入力を高速に読み込むために sys.stdin.read を使用している。
• sum(A) ではなく total_capacity = sum(A) のように変数名をつけることで可読性が向上する。
• 大きな入力に対しては高速な入力処理が重要であることに注意。

ソースコード

import sys

def main():
    input = sys.stdin.read
    data = input().split()
    
    N = int(data[0])
    M = int(data[1])
    A = list(map(int, data[2:]))
    
    total_capacity = sum(A)
    
    if total_capacity >= M:
        print("Yes")
    else:
        print("No")

if __name__ == "__main__":
    main()

この解説は qwen3-coder-480b によって生成されました。