概要

各モンスターとの戦闘結果は、その時点の体力を見れば一意に決まります。
したがって、\(1\) 番目から順番にシミュレーションし、倒せた回数を数えるだけで答えを求められます。

考察

この問題で重要なのは、各戦闘に選択肢がないことです。

モンスター \(i\) に対して、

• 体力が \(H_i\) 以上なら倒して、体力は \(H_i\) 減る
• 体力が \(H_i\) 未満なら倒せず、体力は \(H_i\) 増える

というルールが決まっているので、その場で起こることは完全に一意です。
つまり、「どのモンスターを倒すか選ぶ」「後で別の行動をする」といった要素はありません。

たとえば、初期体力 \(P=10\)、モンスターが \([4,7,3]\) のとき：

1. 最初のモンスター \(4\)：\(10 \ge 4\) なので倒せる
   \(\rightarrow\) 体力は \(10-4=6\)、討伐数は \(1\)
2. 次のモンスター \(7\)：\(6 < 7\) なので倒せない
   \(\rightarrow\) 体力は \(6+7=13\)
3. 次のモンスター \(3\)：\(13 \ge 3\) なので倒せる
   \(\rightarrow\) 体力は \(13-3=10\)、討伐数は \(2\)

よって答えは \(2\) です。

素朴なアプローチについて

この問題では、全探索や動的計画法のような複雑な方法を考える必要はありません。
なぜなら、各時点での行動が固定されており、分岐が存在しないからです。

また、モンスターの順番は固定なので、並べ替えたり、まとめて処理しようとすると誤答になります。
結局、先頭から順番に処理する以外に正しい方法はないので、そのままシミュレーションするのが最も自然で高速です。

アルゴリズム

以下の手順で処理します。

1. 現在の体力を hp = P とする
2. 討伐数 ans = 0 とする
3. モンスターを先頭から順に見ていく
   • もし hp >= H_i なら
     • hp -= H_i
     • ans += 1
   • そうでなければ
     • hp += H_i
4. 最後に ans を出力する

この処理は各モンスターに対して \(1\) 回ずつ行うだけです。

計算量

• 時間計算量: \(O(N)\)
• 空間計算量: \(O(N)\)

※ 実装ではモンスターの強さ配列を保持しているため \(O(N)\) です。
追加で使う作業用の変数は \(O(1)\) です。

実装のポイント

• 体力がちょうど \(0\) になっても探索は続きます。

• 「倒せないときに体力が増える」点を見落とさないようにしましょう。

• 制約が大きく、\(N \le 5 \times 10^5\) なので、入力は sys.stdin.buffer.read() を使うと高速です。

• 体力は増減を繰り返しますが、Python の整数型ならそのまま安全に扱えます。

  ソースコード

import sys

def main():
    data = list(map(int, sys.stdin.buffer.read().split()))
    if not data:
        return
    N, P = data[0], data[1]
    H = data[2:2 + N]

    hp = P
    ans = 0

    for h in H:
        if hp >= h:
            hp -= h
            ans += 1
        else:
            hp += h

    print(ans)

if __name__ == "__main__":
    main()

---

この解説は gpt-5.4-high によって生成されました。