概要

スライムが順番にモンスターと戦い、自分の強さ以下なら吸収して強くなる。最後の強さを求めよ。

考察

スライムは最初に強さ \(W\) を持ち、部屋を順番に進みながらモンスターと出会います。
モンスターの強さがスライムの現在の強さ以下であれば吸収し、スライムの強さに加算されます。
そうでない場合は無視して次へ進みます。

この処理は一見単純に見えますが、モンスターの数 \(N\) が最大 \(2 \times 10^5\) あり、愚直にシミュレーションするとしても特段の工夫は必要ありません。しかし、スライムの強さが指数関数的に増えるわけではないため、途中で吸収できなくなるとそれ以降ずっと吸収できない可能性がある点には注意が必要です。

ただし、この問題では「吸収できるモンスターはすべて吸収する」というシンプルなロジックでシミュレーションすればよいので、特に最適化は必要ありません。
つまり、各モンスターに対して「今の強さ以上なら吸収」する処理を前から順に行うだけで十分です。

アルゴリズム

1. スライムの初期強さ \(W\) を読み込む。
2. 各モンスターの強さ \(V_i\) を順番に読み込みながら、以下の処理を行う：
   • 現在のスライムの強さが \(V_i\) 以上であれば、\(V_i\) を加算する。
3. 最終的なスライムの強さを出力する。

これは単純なループで実現可能であり、特にソートや二分探索などの高度なアルゴリズムは不要です。

例

入力:

5 10
15 8 20 3 12

初期状態：スライムの強さ = 10
- 部屋1（モンスター15）→ 吸収不可 → 強さ: 10
- 部屋2（モンスター8）→ 吸収 → 強さ: 18
- 部屋3（モンスター20）→ 吸収不可 → 強さ: 18
- 部屋4（モンスター3）→ 吸収 → 強さ: 21
- 部屋5（モンスター12）→ 吸収 → 強さ: 33

出力: 33

計算量

• 時間計算量: \(O(N)\)
• 空間計算量: \(O(N)\) （モンスターのリスト保持用）

実装のポイント

• モンスターの配列を前から順に見ていき、条件を満たすものだけを加算していく。
• 変数名は意味がわかりやすいものを選ぶと、コードの可読性が向上します（例：slime_strength）。
• 入力をリストで受け取る際に map(int, input().split()) を使うことで効率よく読み込めます。

## ソースコード

```python
N, W = map(int, input().split())
V = list(map(int, input().split()))

slime_strength = W
for v in V:
    if v <= slime_strength:
        slime_strength += v

print(slime_strength)

---

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