概要

\(N\) 台のサーバーの処理可能回数の合計が \(M\) 日間のリクエスト数以上であれば、すべてのリクエストをさばけるかを判定する問題です。

考察

重要な気づき

各サーバーには処理可能回数 \(A_i\) が設定されており、毎日1件のリクエストをいずれか1台に割り当てます。高橋君は「最適に」割り当てを選べるので、各サーバーの上限を超えない範囲で自由にリクエストを分散できます。

ここで重要なのは、リクエストを割り当てる順番や組み合わせに制約がないことです。つまり、あるサーバーに何日目のリクエストを割り当てるかは自由であり、考えるべきことは「全サーバーの処理可能回数の合計で \(M\) 件をまかなえるか」だけです。

具体例

• \(N = 3, M = 10, A = [3, 4, 5]\) の場合：合計は \(3 + 4 + 5 = 12 \geq 10\) なので Yes
• \(N = 2, M = 10, A = [3, 4]\) の場合：合計は \(3 + 4 = 7 < 10\) なので No

素朴に考えすぎると…

「どのサーバーにどの日のリクエストを割り当てるか」をシミュレーションしようとすると、\(M\) が最大 \(10^9\) と非常に大きいため、1日ずつ処理すると TLE になります。しかし上記の気づきにより、合計値を比較するだけで十分です。

アルゴリズム

1. \(N, M\) を読み込む。
2. 配列 \(A\) を読み込む。
3. \(A_1 + A_2 + \cdots + A_N\) を計算する。
4. 合計が \(M\) 以上なら Yes、そうでなければ No を出力する。

なぜこれで正しいのか：

• 各サーバー \(i\) に \(c_i\) 件（\(0 \leq c_i \leq A_i\)）割り当てるとき、\(c_1 + c_2 + \cdots + c_N = M\) を満たす非負整数の組が存在する条件は、\(\sum A_i \geq M\) です。
• \(\sum A_i \geq M\) であれば、例えばサーバー \(1\) から順に上限まで割り当てていく貪欲法で \(M\) 件をちょうど分配できます。

計算量

• 時間計算量: \(O(N)\)（配列の読み込みと合計の計算）
• 空間計算量: \(O(N)\)（配列の格納）

実装のポイント

• \(A_i\) と \(M\) がそれぞれ最大 \(10^9\)、\(N\) が最大 \(10^5\) なので、合計値は最大 \(10^{14}\) 程度になります。C++ などでは long long を使う必要がありますが、Python では整数のオーバーフローを気にする必要がありません。
• Python の sum() 関数を使えば1行で合計を計算でき、非常に簡潔に書けます。

ソースコード

N, M = map(int, input().split())
A = list(map(int, input().split()))
print("Yes" if sum(A) >= M else "No")

---

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