概要

この問題は、合計 \(M\) コマのシフトを \(N\) 人に割り振る際、各スタッフの「上限コマ数 \(R_i\) と実際の割り当て \(X_i\) の差」の最大値を最小化する問題です。 各スタッフには \(0 \leq X_i \leq R_i\) という制約があり、この範囲内で合計がちょうど \(M\) になるように調整しつつ、不公平度（差の最大値）を抑える必要があります。

考察

1. 不公平度の言い換え

不公平度を \(D\) 以下に抑えたいとします。このとき、すべての \(i\) について以下の条件を満たす必要があります。 $\(R_i - X_i \leq D\)\( これを \)X_i\( について整理すると、以下のようになります。 \)\(X_i \geq R_i - D\)\( もともと \)0 \leq X_i \leq R_i\( という制約があるため、これらを合わせると各スタッフに割り当てるべきコマ数 \)X_i\( の範囲は次のようになります。 \)\(\max(0, R_i - D) \leq X_i \leq R_i\)$

2. 二分探索の利用

「不公平度を \(D\) 以下にできるか？」という判定問題を考えます。 不公平度 \(D\) を小さくすると条件は厳しくなり、大きくすると緩くなるため、答え（不公平度の最小値）について二分探索を適用することができます。

ある \(D\) が実現可能かどうかを判定するには、各スタッフに割り当てる最小限のコマ数 \(\max(0, R_i - D)\) の合計が、目標の \(M\) 以下であればよいです。 （合計が \(M\) 以下であれば、残りの \(M - \sum \max(0, R_i - D)\) コマを各スタッフの \(R_i\) を超えない範囲で適切に上乗せすることで、合計をちょうど \(M\) にできるからです。ただし、そもそも全員の合計上限 \(\sum R_i\) が \(M\) 未満の場合は不可能です。）

3. 判定の高速化

判定のたびに \(N\) 人全員の \(\max(0, R_i - D)\) を計算すると、全体の計算量は \(O(N \log (\max R))\) となり、制約によっては間に合いますが、より効率的に計算できます。 \(R_i\) を昇順にソートしておくと、ある境界 \(k\) を境に： - \(R_i \leq D\) のとき： \(\max(0, R_i - D) = 0\) - \(R_i > D\) のとき： \(\max(0, R_i - D) = R_i - D\) となります。この境界 \(k\) は二分探索（bisect_right）で見つけることができ、後半部分の和は累積和を使って \(O(1)\) で計算可能です。

アルゴリズム

1. 初期チェック: すべての上限の合計 \(\sum R_i\) が \(M\) より小さい場合は、どのように割り当てても合計 \(M\) に届かないため -1 を出力します。
2. 前処理: \(R\) を昇順にソートし、累積和を計算しておきます。
3. 二分探索:
   • 探索範囲: low = 0, high = max(R)
   • 判定関数 check(D):
     • \(R_i > D\) となる最小のインデックス \(k\) を探す。
     • \(R_k\) から \(R_{N-1}\) までの合計から、人数分 \((N-k) \times D\) を引いた値を求める。
     • その値が \(M\) 以下なら True、そうでなければ False。
4. 出力: 判定が True となる最小の \(D\) を出力します。

計算量

• 時間計算量: \(O(N \log N + \log (\max R) \cdot \log N)\)
  • ソートに \(O(N \log N)\) かかります。
  • 二分探索の回数は \(O(\log (\max R))\) 回（約 60 回）で、各判定に \(O(\log N)\) かかるため、十分高速です。
• 空間計算量: \(O(N)\)
  • 配列 \(R\) と累積和配列を保持するために必要です。

実装のポイント

• \(M\) や \(R_i\) が最大 \(10^{18}\) と非常に大きいため、合計値の計算などでオーバーフローに注意する必要があります（Pythonの場合は自動で多倍長整数として扱われるため問題ありません）。

• \(N\) が \(2 \times 10^5\) と大きいため、sys.stdin.read().split() を用いた高速な入出力が推奨されます。

  ソースコード

import sys
from bisect import bisect_right

def solve():
    # Fast I/O: Read all input at once and split into tokens
    try:
        input_data = sys.stdin.read().split()
    except EOFError:
        return
    
    if not input_data:
        return
    
    # N: Number of staff members
    # M: Total number of shifts to be assigned
    N = int(input_data[0])
    M = int(input_data[1])
    
    # R: List of upper limit shifts for each staff member
    # R_i can be up to 10^18, and N up to 2*10^5.
    R = list(map(int, input_data[2:2+N]))
    
    # Sort R to allow for efficient sum calculation using prefix sums and binary search
    R.sort()
    
    # Precompute prefix sums to calculate the sum of any range in O(1)
    prefix_sum = [0] * (N + 1)
    for i in range(N):
        prefix_sum[i+1] = prefix_sum[i] + R[i]
        
    # The total capacity of all staff members must be at least M
    total_capacity = prefix_sum[N]
    if total_capacity < M:
        print("-1")
        return
        
    # Function to calculate the minimum total shifts assigned given a maximum unfairness D.
    # Unfairness D = max(R_i - X_i) implies X_i >= R_i - D for each staff member.
    # Since 0 <= X_i <= R_i, we have max(0, R_i - D) <= X_i <= R_i.
    # To minimize the sum of X_i, we take X_i = max(0, R_i - D).
    def get_min_sum(D):
        # Find the index k such that R[k] > D.
        # For i < k, R[i] - D <= 0, so max(0, R[i] - D) = 0.
        # For i >= k, R[i] - D > 0, so max(0, R[i] - D) = R[i] - D.
        k = bisect_right(R, D)
        count = N - k
        sum_R_k_to_N = prefix_sum[N] - prefix_sum[k]
        # Sum of (R_i - D) for i from k to N-1
        return sum_R_k_to_N - count * D

    # Binary search for the minimum unfairness D in the range [0, max(R)]
    low = 0
    high = R[-1]
    ans = high
    
    while low <= high:
        mid = (low + high) // 2
        # If the minimum required sum for unfairness 'mid' is <= M,
        # it is possible to achieve an unfairness of 'mid' by increasing some X_i.
        if get_min_sum(mid) <= M:
            ans = mid
            high = mid - 1
        else:
            low = mid + 1
            
    print(ans)

if __name__ == "__main__":
    solve()

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