概要

\(N\) 人のスタッフに合計 \(M\) コマのシフトを割り当てるとき、各スタッフの「上限コマ数と実際の割り当ての差」の最大値（不公平度）を最小化する問題です。不公平度の値で二分探索を行うことで効率的に解けます。

考察

重要な気づき：答えで二分探索できる

不公平度を \(d\) と置くと、各スタッフ \(i\) に対して \(R_i - X_i \leq d\) が要求されます。これは \(X_i \geq R_i - d\) を意味します。一方で \(0 \leq X_i \leq R_i\) という制約もあるので、各スタッフの割り当て可能範囲は：

\[\max(0, R_i - d) \leq X_i \leq R_i\]

となります。

合計 \(\sum X_i = M\) を達成するには、最小の合計値 \(\sum \max(0, R_i - d)\) が \(M\) 以下かつ、最大の合計値 \(\sum R_i = S\) が \(M\) 以上であれば可能です。

\(M \leq S\) は事前にチェック済み（違反なら -1）なので、結局 \(d\) が十分大きければ \(\sum \max(0, R_i - d) \leq M\) が成り立つ という単調性があります。つまり、\(d\) を大きくするほど条件は緩くなるため、二分探索で最小の \(d\) を求められます。

素朴なアプローチの問題

\(d\) を固定したとき、\(\sum \max(0, R_i - d)\) を毎回ナイーブに計算すると \(O(N)\) かかり、二分探索と合わせて \(O(N \log(\max R_i))\) になります。これは十分高速ですが、\(\sum \max(0, R_i - d)\) の計算を高速化するために配列をソートして二分探索 + 累積和を使うとさらに見通しが良くなります。

アルゴリズム

1. 不可能判定: \(M > \sum R_i\) なら -1 を出力して終了。
2. ソートと累積和の前計算: \(R\) を昇順にソートし、累積和配列 \(\text{prefix}\) を作る。
3. 答え \(d\) の二分探索: \(d\) の範囲は \([0, \max(R_i)]\) とする。
   • \(d\) を固定したとき、\(R_i > d\) となるスタッフだけが \(R_i - d\) の下限を持つ。ソート済みの \(R\) 上で二分探索し、\(R_i > d\) となる最初のインデックスを求める。
   • 該当するスタッフの \(\sum (R_i - d)\) を累積和で \(O(\log N)\) で計算。
   • この値が \(M\) 以下なら \(d\) は十分大きい（\(d\) を小さくする方向へ）、そうでなければ \(d\) を大きくする。
4. 最終的に求まった \(d\) が答え。

具体例

\(N = 3, M = 7, R = [5, 3, 4]\) の場合、\(S = 12\)。

• \(d = 2\) のとき：下限は \(\max(0, 5-2) + \max(0, 3-2) + \max(0, 4-2) = 3 + 1 + 2 = 6 \leq 7\)。OK。
• \(d = 1\) のとき：下限は \(4 + 2 + 3 = 9 > 7\)。NG。

よって答えは \(d = 2\)。（例: \(X = [5, 0, 2]\) ではなく \(X = [3, 1, 3]\) などが実現可能）

計算量

• 時間計算量: \(O(N \log N + N \log(\max R_i))\)
  • ソートに \(O(N \log N)\)、二分探索の各ステップで内部二分探索 \(O(\log N)\)、外側の二分探索が \(O(\log(\max R_i))\) 回。
• 空間計算量: \(O(N)\)（累積和配列）

実装のポイント

• \(M\) や \(R_i\) が最大 \(10^{18}\) と非常に大きいため、オーバーフローに注意が必要です（Pythonでは多倍長整数なので問題なし）。

• \(\sum \max(0, R_i - d)\) の計算では、ソート済み配列上の二分探索で \(R_i > d\) の範囲を特定し、累積和を使って \(O(\log N)\) で求めるのがポイントです。

• \(M = 0\) の場合は全員に \(0\) コマ割り当て、不公平度は \(\max(R_i)\) となりますが、これも二分探索で自然に求まります。

  ソースコード

import sys

def solve():
    input_data = sys.stdin.buffer.read().split()
    N = int(input_data[0])
    M = int(input_data[1])
    R = [int(input_data[i + 2]) for i in range(N)]
    
    S = sum(R)
    
    # If M > S, impossible since we can't assign more than sum of R_i
    if M > S:
        print(-1)
        return
    
    # If M == S, everyone gets their max, unfairness = 0
    # We need to minimize max(R_i - X_i) where sum(X_i) = M, 0 <= X_i <= R_i
    
    # Binary search on the answer d (unfairness)
    # For a given d, we need: R_i - X_i <= d for all i, i.e., X_i >= R_i - d
    # Also X_i <= R_i and X_i >= 0
    # So X_i >= max(0, R_i - d) and X_i <= R_i
    # 
    # The minimum total assignment = sum(max(0, R_i - d))
    # The maximum total assignment = sum(R_i) = S
    # 
    # We need min_total <= M <= max_total = S
    # Since M <= S is already guaranteed, we just need sum(max(0, R_i - d)) <= M
    
    # We need to find the smallest d >= 0 such that sum(max(0, R_i - d)) <= M
    
    # Sort R to efficiently compute sum(max(0, R_i - d))
    R.sort()
    
    # Prefix sums
    prefix = [0] * (N + 1)
    for i in range(N):
        prefix[i + 1] = prefix[i] + R[i]
    
    def min_total(d):
        # sum of max(0, R_i - d) for all i
        # R is sorted. Find first index where R[idx] > d
        # For R[i] <= d: contribution is 0
        # For R[i] > d: contribution is R[i] - d
        lo, hi = 0, N
        while lo < hi:
            mid = (lo + hi) // 2
            if R[mid] > d:
                hi = mid
            else:
                lo = mid + 1
        # lo = first index where R[idx] > d
        # sum of (R[i] - d) for i in [lo, N-1]
        count = N - lo
        s = prefix[N] - prefix[lo]
        return s - d * count
    
    # Binary search: find smallest d >= 0 such that min_total(d) <= M
    # d ranges from 0 to max(R) (or could be 0 if M >= S which gives d=0... well M==S gives d=0)
    
    # If d = max(R), min_total = 0 <= M always (since M >= 0)
    # If d = 0, min_total = S. We need S <= M, which means M = S (since M <= S). 
    
    # Check if M == 0: then X_i = 0 for all i, unfairness = max(R_i)
    # Actually that's handled by the binary search.
    
    # Edge: if M < 0 shouldn't happen given constraints
    
    lo_d = 0
    hi_d = max(R) if N > 0 else 0
    
    # Check: at d = hi_d, min_total should be <= M
    # min_total(max(R)) = sum(max(0, R_i - max(R))) = 0 <= M. Good.
    
    while lo_d < hi_d:
        mid_d = (lo_d + hi_d) // 2
        if min_total(mid_d) <= M:
            hi_d = mid_d
        else:
            lo_d = mid_d + 1
    
    print(lo_d)

solve()

---

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