概要

スライムが部屋を順番に進みながら、自分の強さ以下のモンスターを吸収して成長していく過程をシミュレーションする問題です。

考察

この問題では、スライムが部屋1から部屋Nまで順番に進んでいく点がポイントです。

重要な気づき

• スライムは各部屋を訪れる順序が固定されている（部屋1→部屋2→…→部屋N）
• 各部屋で「吸収するかしないか」の判定は、その時点でのスライムの強さとモンスターの強さの比較だけで決まる
• 一度吸収したモンスターの強さはスライムに加算され、以降の判定に影響する

素朴なアプローチで問題ないか？

この問題は素朴に各部屋を順番に見ていくだけで解けます。特別なアルゴリズムは必要ありません。

例: \(N=4\), \(W=5\), \(V=[3, 10, 2, 4]\) の場合 1. 部屋1: モンスターの強さ3 ≤ スライムの強さ5 → 吸収！ スライムの強さ = 5 + 3 = 8 2. 部屋2: モンスターの強さ10 > スライムの強さ8 → 吸収できない。スライムの強さ = 8のまま 3. 部屋3: モンスターの強さ2 ≤ スライムの強さ8 → 吸収！ スライムの強さ = 8 + 2 = 10 4. 部屋4: モンスターの強さ4 ≤ スライムの強さ10 → 吸収！ スライムの強さ = 10 + 4 = 14

最終的なスライムの強さは 14 となります。

アルゴリズム

1. スライムの強さを初期値 \(W\) で初期化する
2. 部屋1から部屋Nまで順番に以下を繰り返す：
   • モンスターの強さ \(V_i\) がスライムの現在の強さ以下なら、スライムの強さに \(V_i\) を加算する
   • そうでなければ何もしない
3. 最終的なスライムの強さを出力する

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

このように、問題文の内容をそのまま実装すれば正解が得られます。

計算量

• 時間計算量: \(O(N)\)
  • 各部屋を1回ずつ訪れ、定数時間の処理を行うため
• 空間計算量: \(O(N)\)
  • モンスターの強さを格納する配列 \(V\) のサイズ

実装のポイント

• オーバーフローに注意: \(W\) と \(V_i\) が最大 \(10^9\) で、最大 \(2 \times 10^5\) 個のモンスターを吸収する可能性があるため、最終的な強さは最大約 \(2 \times 10^{14}\) 程度になり得ます。Pythonでは整数のオーバーフローを気にする必要はありませんが、C++などでは long long 型を使用する必要があります。

• 条件式の等号: 問題文に「強さ以下であれば吸収」とあるので、v <= strength と等号を含めることを忘れないようにしましょう。

  ソースコード

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

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

print(strength)

---

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