概要

\(N\) 人のスタッフに \(M\) コマのシフトを割り当てるとき、各スタッフの上限 \(R_i\) を超えない範囲で、不公平度 \(\max (R_i - X_i)\) を最小にする割り当て方を求めよ。条件を満たす割り当てが不可能な場合は -1 を出力せよ。

考察

この問題では、不公平度を最小にすることが目的である。不公平度とは「各スタッフが上限よりどれだけ少ない割り当てを受けているか」の最大値であり、これを最小にすることで、誰も極端に不利にならないようにしたい。

素朴なアプローチの問題点

単純には、各スタッフに均等に割り当てることを考えるが、上限 \(R_i\) が人によって異なるため、単純な均等割り当てでは最適にならない。また、総和が \(M\) ぴったりになるように割り当てる必要があるため、工夫が必要である。

解法の着想

不公平度を固定して、その不公平度で \(M\) コマを割り当てられるかどうかを判定することができれば、二分探索が使える。具体的には、「不公平度が \(d\) 以下である」という条件の下で、各スタッフには最低でも \(X_i = \max(0, R_i - d)\) コマは割り当てることができる。このときの合計が \(M\) 以下であれば、さらに調整して \(M\) にできるのでOK。

逆に、不公平度 \(d\) に対して、\(\sum \max(0, R_i - d) > M\) なら、その \(d\) では割り当てすぎてしまうため、不公平度をもっと小さくする必要がある。

このようにして、不公平度の最小値を二分探索で求めることができる。

アルゴリズム

1. まず、全員に上限まで割り当てたときの合計 \(\sum R_i\) が \(M\) 未満なら、条件を満たす割り当ては不可能 → -1 を出力。
2. 二分探索により、不公平度 \(d\) の最小値を求める。
   • 探索範囲：\(d = 0\) 〜 \(\max(R_i)\)
   • 各 \(d\) について、\(\sum \max(0, R_i - d)\) を計算し、それが \(M\) 以下かどうかを判定。
   • 条件を満たす最小の \(d\) を求める。

計算量

• 時間計算量: \(O(N \log(\max(R_i)))\)
• 空間計算量: \(O(1)\)（入力を除く）

※二分探索の各ステップで配列全体を走査する必要があり、それが \(O(N)\)、探索回数が \(O(\log(\max(R_i)))\) 回。

実装のポイント

• 二分探索の終了条件 left <= right を守ること。
• max(0, R[i] - d) の計算を忘れずに。
• 入力が非常に大きいため、sys.stdin.read を使用して高速に読み込むとよい。
• 合計値が非常に大きくなる可能性があるため、Pythonの整数型は安全に扱える。

## ソースコード

```python
def main():
    import sys
    input = sys.stdin.read
    data = input().split()
    
    N = int(data[0])
    M = int(data[1])
    R = list(map(int, data[2:]))
    
    # 総和チェック: 割り当て可能か
    total_max = sum(R)
    if M > total_max:
        print(-1)
        return
    
    # 割り当て不能なケース（Mが負でもないかチェック）
    if M < 0:
        print(-1)
        return

    # 不公平度を最小化するには、各R[i] - X[i] の最大値を最小にする
    # つまり、X[i] = max(0, R[i] - d) のように設定し、sum(X) == M となるような最小のdを探す
    
    # 二分探索でdの最小値を求める
    def is_possible(d):
        # 各スタッフに割り当て可能な最大は R[i]
        # 不公平度がd以下にするには、X[i] >= R[i] - d
        # かつ X[i] >= 0, X[i] <= R[i]
        # よって X[i] = max(0, R[i] - d) から R[i] の間で調整可能
        assigned = 0
        for r in R:
            x = max(0, r - d)
            assigned += x
        return assigned <= M  # 割り当てすぎていないか

    # dの探索範囲: 0 から max(R)
    left = 0
    right = max(R) if R else 0
    answer = -1

    while left <= right:
        mid = (left + right) // 2
        # d=midで達成できる最小割り当てを試す
        min_assigned = sum(max(0, r - mid) for r in R)
        if min_assigned <= M:
            answer = mid
            right = mid - 1
        else:
            left = mid + 1

    print(answer)

if __name__ == "__main__":
    main()

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