概要

高橋君がダンジョンの最上階に到達するために必要な強化薬の最小個数を求める問題です。強化薬を使うと初期戦闘力を上げることができ、各階層のモンスターを倒す条件を満たす必要があります。

考察

問題の核心は、強化薬を何個使えば全ての階層を突破できるかを判定することです。素朴なアプローチとして、強化薬を0個からK個まで順番に試す方法が考えられますが、Kが最大\(10^{18}\)にもなるため、全探索は明らかに不可能です。

重要な観察は、強化薬をx個使ったときの初期戦闘力がS+xであり、これが十分大きければ全てのモンスターを倒せるという単調性があることです。つまり、xが小さいときは途中で敗北し、xがある値以上になると必ずクリアできるという性質があります。この単調性を利用することで、二分探索によって効率的に最小のxを見つけることができます。

アルゴリズム

1. まず強化薬を0個使った場合（初期戦闘力S）でクリアできるか判定します。できる場合は0を出力します。
2. 次に強化薬を最大数K個使った場合でもクリアできない場合は-1を出力します。
3. それ以外の場合は、二分探索を行います。探索範囲は[0, K]とし、各中間点midについてcan_reach(mid)関数でクリア可能かを判定します。
   • can_reach(x)関数：初期戦闘力をS+xに設定し、各階層のモンスターを順番に戦っていきます。現在の戦闘力がモンスターの強さ以上なら戦闘力を加算し、そうでなければfalseを返します。全ての階層を突破できたらtrueを返します。
4. 二分探索で見つかった最小のxが答えとなります。

計算量

• 時間計算量: \(O(N \log K)\)
  • 二分探索の反復回数は\(\log K\)回
  • 各反復でN階層分の判定を行うため\(O(N)\)
  • 合わせて\(O(N \log K)\)
• 空間計算量: \(O(N)\)
  • モンスターの強さを格納する配列の分

実装のポイント

• 二分探索の初期条件として、0個とK個の場合を先に判定することで無駄な計算を省いています。

• can_reach関数内で現在の戦闘力を更新する際、加算処理を行うことでモンスターを倒した後の戦闘力の変化を正しくシミュレートしています。

• 大きな数値（最大\(10^{18}\)）を扱うため、整数オーバーフローに注意する必要がありますが、Pythonでは自動で多倍長整数を扱えるため問題ありません。

  ソースコード

import sys

def main():
    data = sys.stdin.read().split()
    if not data:
        print(-1)
        return
        
    N = int(data[0])
    S = int(data[1])
    K = int(data[2])
    E = list(map(int, data[3:3+N-1]))
    
    left = 0
    right = K
    answer = -1
    
    def can_reach(x):
        current = S + x
        for i in range(N-1):
            if current < E[i]:
                return False
            current += E[i]
        return True
    
    if can_reach(0):
        print(0)
        return
        
    if not can_reach(K):
        print(-1)
        return
        
    while left <= right:
        mid = (left + right) // 2
        if can_reach(mid):
            answer = mid
            right = mid - 1
        else:
            left = mid + 1
            
    print(answer)

if __name__ == "__main__":
    main()

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