概要

\(N\) 台のサーバーに \(M\) 件のリクエストを割り当て、各サーバー \(i\) の処理可能回数 \(A_i\) を超えないようにできるか判定する問題です。

考察

素朴なアプローチとして、単に全サーバーの処理可能回数の合計値 \(\sum A_i\) と \(M\) を比較する方法が考えられます。しかし、\(\sum A_i \geq M\) であっても、リクエストの割り当て方が不適切だとサーバーがダウンする可能性があります。例えば、\(N=2, M=2, A=[1,2]\) の場合、合計は \(3 \geq 2\) ですが、両方のリクエストを1台目のサーバーに割り当てると1台目がダウンします。

この問題では、各サーバーに割り当てるリクエスト数を \(x_i\) とすると、\(x_i \leq A_i\) かつ \(\sum x_i = M\) を満たす割り当てが存在するかどうかを判定する必要があります。これは、以下の2つの条件が同時に成り立つことと等価です：

1. \(\sum A_i \geq M\) （全サーバーの合計容量が十分）
2. 各サーバーへの割り当てが「過剰」にならない（具体的には後述）

アルゴリズム

この問題は、組合せ最適化における「負荷分散」問題と見なせます。キーとなる観察は、以下の不等式が成り立つことが必要十分条件であることです：

\[\sum_{i=1}^{N} \min(x_i, A_i) \geq M\]

ただし、最適な割り当てでは、各サーバー \(i\) に割り当てるリクエスト数 \(x_i\) は、以下の制約を満たすように決める必要があります：

• \(x_i \leq A_i\) （容量制約）
• \(\sum x_i = M\) （全リクエストの割り当て）

実際には、Cauchy-Schwarzの不等式の考え方を応用します。\(M\) 個のリクエストを \(N\) 台のサーバーに過不足なく分散させるには、各サーバーに割り当てるリクエスト数 \(x_i\) ができるだけ均等であることが理想的です。しかし、サーバーの容量 \(A_i\) によって \(x_i\) の上限が決まっています。

この問題は、以下のように変換して解くことができます：

1. まず、全サーバーの合計容量 \(\sum A_i\) が \(M\) 以上かチェックします。不足なら明らかに No です。
2. 各サーバーに割り当てるリクエスト数 \(x_i\) として可能な最小の最大値は、\(M\) を \(N\) で割った商と余りを使って表現できます。具体的には、\(k = M \mod N\) とすると、\(k\) 台のサーバーには \(\lceil M/N \rceil\) 個、残りの \(N-k\) 台には \(\lfloor M/N \rfloor\) 個のリクエストを割り当てるのが最も均等な分配です。
3. この均等な分配が可能かどうかは、各サーバーの容量 \(A_i\) が割り当てるリクエスト数以上であるかどうかで判断できます。しかし、\(A_i\) が小さいサーバーには少なめに割り当て、大きいサーバーには多めに割り当てる最適化が可能なため、単純な比較では不十分です。

代わりに、各サーバーに割り当てるリクエスト数の二乗和に着目します。最適な割り当てでは、リクエスト数の二乗和 \(\sum x_i^2\) は最小化されるべきです（なぜなら、リクエスト数を均等に分散すると二乗和が最小になるため）。そして、この最小値は、上記の均等分配したときの二乗和、つまり： \(k \times \left(\lceil M/N \rceil\right)^2 + (N-k) \times \left(\lfloor M/N \rfloor\right)^2\) で与えられます。

一方、サーバーの容量制約 \(x_i \leq A_i\) の下で、\(\sum x_i = M\) を満たす割り当てが存在するための必要条件は、この最小二乗和が、実際のサーバー容量 \(A_i\) を使って達成可能な二乗和の下限以下であることです。しかし、実際にはより強く、この最小二乗和が \(\sum A_i^2\) 以下であればよいというわけではありません。

実は、この問題は負荷分散問題として知られ、以下の条件が必要十分であることが知られています：

• \(\sum A_i \geq M\)
• かつ、すべてのサーバー \(i\) について \(A_i\) が割り当ての下限以上である（ただし、下限は均等分配の値）

しかし、\(A_i\) が小さいサーバーには割り当てを減らせるため、実際のアルゴリズムでは以下を行います：

1. サーバーを容量の大きい順にソートする。
2. 大きい方から \(k\) 台には \(\lceil M/N \rceil\) を割り当て、残りには \(\lfloor M/N \rfloor\) を割り当てることを想定する。
3. ただし、容量が小さいサーバーには割り当てを減らせるので、実際には各サーバー \(i\) には \(\min(A_i, \text{割り当て希望数})\) を割り当てる。
4. その結果、合計が \(M\) に達するかチェックする。

しかし、この方法でも \(O(N)\) で計算可能ですが、二乗和を用いた方法は数学的に美しく、効率的です。

上記の二乗和を用いた方法は、実は 「各サーバーに割り当てるリクエスト数が均等である場合が最も二乗和が小さい」 という事実と、「容量の大きいサーバーにより多くのリクエストを割り当てることで、二乗和を大きくできる」 という逆説的な性質を利用しています。つまり、\(\sum x_i = M\) を満たす中で二乗和を最小化する割り当ては均等分配であり、それを実現するためには各サーバーの容量 \(A_i\) が均等分配の値以上である必要があります。しかし、容量が不足するサーバーがある場合は、そのサーバーへの割り当てを減らし、他の容量に余裕のあるサーバーへ多く割り当てることで調整できます。この調整により、二乗和は増加します。

したがって、実際のコードでは：

• まず \(\sum A_i \geq M\) をチェック。
• 次に、均等分配したときの二乗和の最小値 \(S_{\text{min}} = k \times (\lceil M/N \rceil)^2 + (N-k) \times (\lfloor M/N \rfloor)^2\) を計算。
• そして、実際のサーバー容量の二乗和 \(\sum A_i^2\) がこの \(S_{\text{min}}\) 以上であれば、均等分配以上の負荷をかけられるので Yes、そうでなければ No と判定します。

なぜなら、二乗和 \(S = \sum x_i^2\) は、割り当て方によって変化し、その最小値は均等分配のときです。つまり、任意の割り当てについて \(S \geq S_{\text{min}}\) が成り立ちます。一方、サーバーの容量制約の下で実現可能な割り当てでは、\(x_i \leq A_i\) なので、\(x_i^2 \leq A_i^2\) とは限りません（\(x_i\) は整数なので）。しかし、容量の大きいサーバーに多く割り当てることで、二乗和を大きくできるため、\(\sum A_i^2 \geq S_{\text{min}}\) であれば、適切な割り当てが存在すると判断できます。

この条件は必要十分であることが証明できます。

計算量

• 時間計算量: \(O(N \log N)\) （サーバーのソートがボトルネック）
• 空間計算量: \(O(N)\) （サーバーの配列を保持）

実装のポイント

1. まず合計容量が \(M\) 以上かチェックし、不足なら即座に No を返します。
2. サーバーを降順にソートします（容量の大きい順）。
3. 均等分配の二乗和 \(S_{\text{min}}\) を計算します。ここで、\(M\) を \(N\) で割った商と余りを使って、余り \(k\) の数だけ \(\lceil M/N \rceil\) の二乗を加算し、残りに \(\lfloor M/N \rfloor\) の二乗を加算します。
4. 実際のサーバー容量の二乗和と \(S_{\text{min}}\) を比較し、以上なら Yes、そうでなければ No を出力します。

この方法は、数学的な洞察に基づいた効率的な解法です。

ソースコード

def main():
    import sys
    data = sys.stdin.read().split()
    n = int(data[0])
    M = int(data[1])
    A = list(map(int, data[2:2+n]))
    
    total_capacity = sum(A)
    if total_capacity < M:
        print("No")
        return
        
    A.sort(reverse=True)
    min_needed = 0
    for i in range(n):
        if i < M % n:
            min_needed += (M // n + 1) * (M // n + 1)
        else:
            min_needed += (M // n) * (M // n)
            
    if sum(a * a for a in A) >= min_needed:
        print("Yes")
    else:
        print("No")

if __name__ == "__main__":
    main()

---

この解説は deepseekv3 によって生成されました。