概要

初期戦闘力 \(S\) に強化薬を \(x\) 個足した状態で、各階層のモンスター（強さ \(E_i\)）を倒しながら最上階を目指す問題です。モンスターを倒すとその強さが自分の戦闘力に加算されるというルールのもと、全てのモンスターを倒すために必要な最小の \(x\) を求めます。

考察

高橋君が階層 \(i\) に到達したときの戦闘力を考えてみましょう。 強化薬を \(x\) 個使うと、最初の戦闘力は \(S + x\) です。

• 階層 1 での戦闘力：\(P_1 = S + x\)
• 階層 2 での戦闘力：\(P_2 = (S + x) + E_1\) （階層 1 のモンスターを倒した後）
• 階層 3 での戦闘力：\(P_3 = (S + x) + E_1 + E_2\)
• 階層 \(i\) での戦闘力：\(P_i = (S + x) + \sum_{j=1}^{i-1} E_j\)

階層 \(i\) のモンスターを倒して次の階層へ進むための条件は \(P_i \geq E_i\) です。 この式に上記の \(P_i\) を代入して、\(x\) について整理してみます。

\((S + x) + \sum_{j=1}^{i-1} E_j \geq E_i\) \(x \geq E_i - S - \sum_{j=1}^{i-1} E_j\)

この式は、「階層 \(i\) を突破するためには、強化薬が最低でも \(E_i - S - \sum_{j=1}^{i-1} E_j\) 個必要である」ということを示しています。

全ての階層（\(i = 1, 2, \ldots, N-1\)）を突破するためには、各階層で計算される「必要な \(x\)」の最大値を用意すればよいことになります。ただし、もともとの戦闘力で十分な場合（計算結果が 0 以下のとき）は強化薬を使う必要がないため、 \(x\) の下限は 0 です。

アルゴリズム

1. 必要な強化薬の最大値 max_x を 0 で初期化します。
2. これまでに倒したモンスターの強さの合計 prefix_sum_E を 0 で初期化します。
3. \(i = 1\) から \(N-1\) まで、各階層のモンスター \(E_i\) について以下を繰り返します：
   • その階層を突破するために必要な \(x\) の値 needed を計算します。 needed = E[i] - S - prefix_sum_E
   • needed が現在の max_x より大きければ、 max_x を更新します。
   • prefix_sum_E に現在のモンスターの強さ \(E_i\) を加算します。
4. 最終的な max_x が \(K\) 以下であれば max_x を出力し、そうでなければ -1 を出力します。

計算量

• 時間計算量: \(O(N)\) 階層の数 \(N\) に対して、1 回のループで各モンスターを処理するため、線形時間で計算が終わります。
• 空間計算量: \(O(N)\) 入力されたモンスターの強さをリストに格納するために \(O(N)\) のメモリを使用します。

実装のポイント

• 大きな数値の扱い: \(K\) や \(E_i\) の累積和は非常に大きな値（最大で \(10^{18}\) 程度）になりますが、Python では整数の大きさに制限がないため、オーバーフローを気にせずそのまま計算できます。

• 高速な入力: \(N = 2 \times 10^5\) と入力サイズが大きいため、input() を繰り返すよりも sys.stdin.read().split() を使って一括で読み込む方が実行時間を短縮できます。

  ソースコード

import sys

def solve():
    # 入力を一括で読み込み、スペースや改行で分割します。
    # N=2*10^5 程度の入力サイズであれば、sys.stdin.read().split() が高速です。
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    # ダンジョンの階層数 N、初期戦闘力 S、強化薬の最大使用個数 K を取得
    N = int(input_data[0])
    S = int(input_data[1])
    K = int(input_data[2])
    
    # 各階層のモンスターの強さ E_1, ..., E_{N-1} をリストに格納
    # E の要素数は N-1 個です。
    E = list(map(int, input_data[3:]))
    
    # 高橋君が階層 N に到達するために必要な追加の戦闘力（強化薬の使用個数）の最大値を保持します。
    # 初期値は 0（強化薬を使わなくても進める状態）とします。
    max_x = 0
    # これまでに倒したモンスターの強さの合計（戦闘力の上昇分）を保持します。
    prefix_sum_E = 0
    
    # 階層 1 から N-1 までの各階層についてシミュレーションします。
    # 階層 i に到達した時点での戦闘力 P_i は、
    # P_i = (初期戦闘力 S + 強化薬の使用個数 x) + (階層 1 から i-1 までのモンスターの強さの合計)
    # となります。
    # 階層 i+1 に進むための条件は P_i >= E_i です。
    # これを変形すると、 x >= E_i - S - (階層 1 から i-1 までのモンスターの強さの合計)
    # となります。
    
    for i in range(N - 1):
        # 現在の階層のモンスターの強さ E[i] に対して必要な x を計算します。
        # needed = E_i - S - prefix_sum_E
        needed = E[i] - S - prefix_sum_E
        
        # 全ての階層を突破するために、x は各階層で求められる needed の最大値以上である必要があります。
        if needed > max_x:
            max_x = needed
        
        # モンスターを倒すとその強さが戦闘力に加算されます。
        prefix_sum_E += E[i]
        
    # 求まった最小の x が、与えられた強化薬の最大個数 K 以内であるか判定します。
    if max_x <= K:
        print(max_x)
    else:
        # K 個以内で到達できない場合は -1 を出力します。
        print(-1)

if __name__ == '__main__':
    solve()

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