概要

ダンジョンの全階層を突破するために必要な最小の初期戦闘力を数学的に求め、それと現在の初期戦闘力 \(S\) との差から、必要な強化薬の個数を計算する問題です。

考察

重要な気づき：戦闘力の累積構造

高橋君がモンスターを倒すたびに、そのモンスターの強さ分だけ戦闘力が増加します。つまり、\(i\) 番目のモンスター（0-indexed）と戦う直前の戦闘力は：

\[P_i = S_{\text{init}} + \sum_{j=0}^{i-1} E_j\]

ここで \(S_{\text{init}} = S + x\)（\(x\) は使用する強化薬の個数）です。各モンスターを倒す条件は \(P_i \geq E_i\) なので：

\[S_{\text{init}} + \underbrace{\sum_{j=0}^{i-1} E_j}_{\text{prefix}[i]} \geq E_i\]

これを変形すると：

\[S_{\text{init}} \geq E_i - \text{prefix}[i]\]

この条件がすべての \(i = 0, 1, \ldots, N-2\) について成り立てばよいので、必要な最小初期戦闘力は：

\[S_{\text{init}}^{\min} = \max\left(0,\ \max_{0 \leq i \leq N-2} \left(E_i - \text{prefix}[i]\right)\right)\]

具体例

例えば \(N=4\), \(S=3\), \(E = [2, 5, 3]\) の場合：

\(i\)	\(E_i\)	\(\text{prefix}[i]\)	\(E_i - \text{prefix}[i]\)
0	2	0	2
1	5	2	3
2	3	7	-4

\(S_{\text{init}}^{\min} = \max(0, 2, 3, -4) = 3\) なので、\(S = 3\) ならば強化薬は \(0\) 個で突破できます。

素朴なアプローチとの比較

強化薬の個数 \(x\) を \(0\) から \(K\) まで順に試してシミュレーションすると、\(K\) が最大 \(10^{18}\) にもなるため到底間に合いません。二分探索を使う方法もありますが、上記の数式により \(O(N)\) で直接計算 できるため、それすら不要です。

アルゴリズム

1. \(\text{prefix} = 0\), \(\text{min\_S\_init} = 0\) で初期化する。
2. \(i = 0, 1, \ldots, N-2\) について順に：
   • \(\text{needed} = E_i - \text{prefix}\) を計算し、\(\text{min\_S\_init}\) を更新。
   • \(\text{prefix}\) に \(E_i\) を加算。
3. 必要な強化薬の個数は \(x = \text{min\_S\_init} - S\)。
   • \(x \leq 0\) ならば 0 を出力（強化不要）。
   • \(0 < x \leq K\) ならば \(x\) を出力。
   • \(x > K\) ならば -1 を出力。

計算量

• 時間計算量: \(O(N)\) — 配列を一度走査するだけ
• 空間計算量: \(O(N)\) — 入力の \(E\) を保持する分（prefix sum は変数1つで管理）

実装のポイント

• \(K\) が最大 \(10^{18}\) と非常に大きいため、ループで全探索するのではなく閉じた式で直接計算する必要があります。

• \(E_i\) や prefix sum が大きくなりうるため、Python のように多倍長整数を扱える言語だとオーバーフローの心配がありません。C++ などでは long long を使う必要があります。

• \(\text{min\_S\_init}\) は負になりえないことに注意し、\(0\) との max を取ります（初期戦闘力は少なくとも \(S \geq 1\) なので実質問題になりませんが、論理的な正しさのために必要です）。

  ソースコード

import sys

def can_clear(S, E):
    P = S
    for e in E:
        if P < e:
            return False
        P += e
    return True

def solve():
    input_data = sys.stdin.buffer.read().split()
    N = int(input_data[0])
    S = int(input_data[1])
    K = int(input_data[2])
    E = [int(input_data[3 + i]) for i in range(N - 1)]
    
    # Binary search on the number of potions used
    # If we use x potions, initial power = S + x
    # We need to find minimum x in [0, K] such that we can clear all floors
    
    # Check if even with K potions we can clear
    # First, find the minimum S_init needed to clear
    # With S_init, we go through floors:
    # After floor 1: P = S_init + E[0] (if S_init >= E[0])
    # After floor i: P = S_init + sum(E[0..i-1]) (if at each step P >= E[i])
    # At floor i, P = S_init + sum(E[0..i-2]), need P >= E[i-1]
    # i.e., S_init >= E[i-1] - sum(E[0..i-2]) for all i from 1 to N-1
    # i.e., S_init >= max over i of (E[i] - prefix_sum[i]) where indexing adjusted
    
    # Let's compute: before fighting monster at floor i (0-indexed),
    # P = S_init + sum(E[0..i-1]) for i >= 1, P = S_init for i = 0
    # Need P >= E[i], i.e., S_init + prefix[i] >= E[i]
    # i.e., S_init >= E[i] - prefix[i]
    # where prefix[0] = 0, prefix[i] = E[0] + ... + E[i-1]
    
    # So minimum S_init = max(0, max over i in 0..N-2 of (E[i] - prefix[i]))
    
    prefix = 0
    min_S_init = 0
    for i in range(N - 1):
        needed = E[i] - prefix
        if needed > min_S_init:
            min_S_init = needed
        prefix += E[i]
    
    # min_S_init is the minimum initial power needed
    # We have S + x >= min_S_init, so x >= min_S_init - S
    
    potions_needed = min_S_init - S
    if potions_needed <= 0:
        print(0)
    elif potions_needed <= K:
        print(potions_needed)
    else:
        print(-1)

solve()

---

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