概要

スライムが \(N\) 個の部屋を順番に巡り、自分より強さが「以下の」モンスターを吸収して成長していく様子をシミュレーションし、最終的なスライムの強さを求める問題です。

考察

この問題で重要な点は、スライムが部屋を移動する順番が 「1番目から \(N\) 番目まで固定されている」 ことです。

スライムの強さはモンスターを吸収するたびに増加します。ある部屋 \(i\) でモンスターを吸収できるかどうかは、それまでの部屋（\(1\) から \(i-1\) 番目）でどれだけモンスターを吸収して強くなっているかに依存します。

しかし、スライムは必ず番号の小さい順に部屋を訪れるため、以下の手順で素直にシミュレーションを行うだけで正解を導き出すことができます。

1. 現在のスライムの強さを変数（current_strength）に持つ。
2. 部屋 \(1\) から \(N\) まで順番に見ていく。
3. その部屋のモンスターの強さ \(V_i\) が current_strength 以下なら、current_strength に \(V_i\) を加算する。
4. そうでなければ、何もしない。

制約を確認すると、部屋の数 \(N\) は最大 \(2 \times 10^5\) です。このシミュレーションは各部屋に対して 1 回ずつの判定と加算を行うだけなので、全体の計算量は \(N\) に比例し、制限時間内に十分間に合います。

アルゴリズム

1. スライムの初期の強さ \(W\) を入力し、現在の強さを表す変数 current_strength に代入します。
2. モンスターの強さのリスト \(V\) を受け取ります。
3. ループ（for 文）を用いて、部屋 \(i = 0\) から \(N-1\) まで以下の処理を繰り返します。
   • もし \(V_i \le \text{current\_strength}\) ならば：
     • current_strength = current_strength + \(V_i\)
4. ループ終了後の current_strength を出力します。

計算量

• 時間計算量: \(O(N)\)
  • 部屋の数 \(N\) に対して、1 回ずつループを回して判定と加算を行うためです。
• 空間計算量: \(O(N)\)
  • モンスターの強さをリスト \(V\) としてメモリに保持する場合の計算量です。

実装のポイント

• 大きな数値の扱い: 最終的なスライムの強さは、初期値 \(10^9\) に最大 \(2 \times 10^5\) 個の \(10^9\) が加算される可能性があるため、約 \(2 \times 10^{14}\) 程度の大きさになります。Python では整数の大きさに制限がないため問題ありませんが、C++ などの言語を使用する場合は 64 ビット整数型（long long）を使用する必要があります。

• 入力の高速化: \(N\) が \(2 \times 10^5\) と比較的大きいため、Python では sys.stdin.read().split() などを使って一括で入力を読み込むと実行時間を短縮できます。

  ソースコード

import sys

def solve():
    # 入力をすべて読み込む
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    # N: 部屋の数, W: スライムの初期の強さ
    n = int(input_data[0])
    current_strength = int(input_data[1])
    
    # V: 各部屋のモンスターの強さ
    v = input_data[2:]
    
    # 各部屋を順番に回る
    for i in range(n):
        monster_strength = int(v[i])
        # モンスターの強さがスライムの現在の強さ以下なら吸収する
        if monster_strength <= current_strength:
            current_strength += monster_strength
            
    # 最終的なスライムの強さを出力
    print(current_strength)

if __name__ == "__main__":
    solve()

この解説は gemini-3-flash-thinking によって生成されました。