概要

部屋を順に進み、現在の強さ以下のモンスターだけを吸収して強さを増やしていくとき、最後のスライムの強さを求める問題です。

考察

この問題のポイントは、スライムの行動が 「部屋 \(1\) から \(N\) まで順番に見る」 ことに完全に固定されている点です。
つまり、各部屋で必要なのは次の判定だけです：

• もし \(V_i \leq\) 現在の強さ なら吸収して強さが \(+\) \(V_i\)
• そうでなければ何も起きない（通り過ぎる）

ここで「吸収できなかったモンスターを後で戻って吸収する」などの行動はできませんし、順序を変えることもできません。したがって、各部屋の処理はその時点の強さだけで決まり、シミュレーション（逐次処理）をそのまま行えば正解です。

素朴というより「そのままの実装」が最適で、変に工夫して探索や並べ替えをすると逆に条件（順番固定）を壊してWAの原因になります。

例： - 初期 \(W=10\), モンスター \([3, 15, 7]\) - \(3 \le 10\) なので吸収 → \(W=13\) - \(15 > 13\) なので吸収できない → \(W=13\) - \(7 \le 13\) なので吸収 → \(W=20\) - 答えは \(20\)

アルゴリズム

1. 現在の強さ cur を初期値 \(W\) で初期化する。
2. \(i=1\) から \(N\) まで順にモンスターの強さ \(V_i\) を見る。
3. もし \(V_i \le cur\) なら cur += V_i として吸収する。
4. 最後に cur を出力する。

この手順は問題文の挙動をそのまま再現したシミュレーションです。

計算量

• 時間計算量: \(O(N)\)（各モンスターを1回ずつ見るだけ）
• 空間計算量: \(O(1)\)（入力配列を除けば、保持するのは現在値のみ）

実装のポイント

• \(N\) が最大 \(2 \times 10^5\) なので、Pythonでは sys.stdin.buffer.read() でまとめて読み込むと安定して高速です。

• 強さは最大で加算により大きくなりますが、Pythonの整数はオーバーフローしないので安心して加算できます。

• 条件は \(V_i \le cur\)（等号を含む）である点に注意します。

  ソースコード

import sys

def main():
    data = list(map(int, sys.stdin.buffer.read().split()))
    N, W = data[0], data[1]
    V = data[2:2+N]
    cur = W
    for x in V:
        if x <= cur:
            cur += x
    print(cur)

if __name__ == "__main__":
    main()

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