概要

スライムがモンスターを順番に吸収していくシミュレーション問題で、現在のスライムの強さ以下のモンスターのみを吸収して強さを加算していきます。

考察

この問題は、スライムが各部屋を順番に移動しながら、現在の強さ以下のモンスターを吸収していく単純なシミュレーションです。重要な点は、吸収できるかどうかの判断が「現在のスライムの強さ」に対して行われることです。つまり、吸収するたびにスライムの強さが増加するため、後からより強いモンスターを吸収できる可能性が出てきます。

素朴なアプローチとして、各部屋を順番に処理していく方法が考えられます。これは問題の制約上、十分に効率的です。なぜなら、\(N\) の最大値が \(2 \times 10^5\) であり、単純なループ処理でも \(O(N)\) で計算できるからです。

アルゴリズム

アルゴリズムは以下のように非常にシンプルです： 1. 初期強さ \(W\) を current にセット 2. 各部屋のモンスター強さ \(V_i\) を順番に処理 3. 各モンスターについて、\(V_i \leq\) current なら current に \(V_i\) を加算 4. すべての部屋を処理した後の current を出力

このアルゴリズムは、スライムの強さが単調増加する性質を利用しています。一度吸収したモンスターの強さは永久にスライムに加算されるため、後続のモンスターを吸収しやすくなっていきます。

計算量

• 時間計算量: \(O(N)\)
  • \(N\) 個のモンスターを1回ずつ処理するため
• 空間計算量: \(O(N)\)
  • モンスターの強さを格納する配列分のメモリを使用

実装のポイント

実装上の注意点は以下の通りです： - 入力値の範囲に注意（\(W\) と \(V_i\) は最大 \(10^9\) まで） - 整数演算のみで処理可能 - 現在の強さを更新する際、加算処理だけでよく減算は発生しない - 入力の読み込み時に、すべてのデータを一度に読み込むことで効率化

ソースコード

def main():
    import sys
    data = sys.stdin.read().split()
    n = int(data[0])
    w = int(data[1])
    V = list(map(int, data[2:2+n]))
    
    current = w
    for v in V:
        if v <= current:
            current += v
            
    print(current)

if __name__ == "__main__":
    main()

この解説は deepseekv3 によって生成されました。