概要

高橋君がダンジョンの最上層に到達するために必要な強化薬の最小使用回数を求める問題です。

考察

この問題では、初期戦闘力 \(S\) に対して強化薬を最大 \(K\) 個まで使って、すべてのモンスターを倒せるようにしなければなりません。

単純な試行では困難

例えば、強化薬を1つずつ増やしながら実際にシミュレーションすると、最悪ケースで非常に時間がかかります（最大 \(K\) 回のシミュレーションが必要）。これは \(K\) が最大 \(10^{18}\) なので、現実的ではありません。

重要な観察

強化薬を使った後の初期戦闘力が \(P = S + x\) （\(x\) は使った強化薬の数）であるとき、
もし \(x\) 個の強化薬で全モンスターを倒せたなら、より多くの強化薬を使っても必ず倒せます。
つまり、「ある数の強化薬で成功する」かどうかという条件は単調性を持っています。

この単調性を利用することで、二分探索によって最小の強化薬使用回数を効率的に求めることができます。

アルゴリズム

1. 強化薬の使用回数を mid として、二分探索を行います。
2. 各 mid に対して、初期戦闘力を \(S + mid\) として、すべてのモンスターを倒せるかシミュレーションします。
3. 倒せた場合、もっと少ない強化薬でも大丈夫かもしれないため、探索範囲を減らします（right = mid - 1）。
4. 倒せなかった場合、もっと多くの強化薬が必要なので、left = mid + 1 とします。
5. 最終的に、条件を満たす最小の mid を求めます。

計算量

• 時間計算量: \(O(N \log K)\)
  • 二分探索が \(O(\log K)\) 回行われ、それぞれで \(O(N)\) のシミュレーションが必要。
• 空間計算量: \(O(N)\)
  • モンスターの強さを格納する配列のサイズ。

実装のポイント

• 二分探索の範囲は left = 0, right = min(K, 10**18) と設定する（\(K\) が非常に大きい場合に備える）。
• 戦闘力の更新は current_power += e で行い、オーバーフローに注意（Pythonでは問題なし）。
• 条件を満たさない場合は -1 を出力することを忘れない。

## ソースコード

```python
import sys
import heapq

def main():
    import sys
    input = sys.stdin.read
    data = input().split()
    
    N = int(data[0])
    S = int(data[1])
    K = int(data[2])
    
    E = list(map(int, data[3:]))

    # Binary search on the number of enhancement potions needed
    left, right = 0, min(K, 10**18)
    answer = -1
    
    while left <= right:
        mid = (left + right) // 2
        current_power = S + mid
        
        success = True
        for e in E:
            if current_power >= e:
                current_power += e
            else:
                success = False
                break
        
        if success:
            answer = mid
            right = mid - 1
        else:
            left = mid + 1
            
    print(answer)

if __name__ == "__main__":
    main()

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