概要

山頂までのN個の区間を順に通過する際、体力を消費しながら山小屋で回復する過程で、バテ状態の変化を考慮して最終的な残り体力を求める問題です。

考察

この問題では、各区間を通過する際に以下の3ステップを順番に処理する必要があります： 1. 現在の状態（バテているかどうか）に応じて体力を消費 2. 体力が0以下でまだバテていない場合、バテ状態に移行 3. 山小屋があれば回復

重要な点は、バテ状態は一度なると解除されないこと、体力消費とバテ判定の順序、回復は上限なく行われることです。素朴にシミュレーションするだけで解けますが、入力サイズが最大20万と大きいため、効率的な実装が必要です。

アルゴリズム

1. 入力データを読み込み、各区間の難易度と各位置の回復量を配列に格納
2. 初期体力Sとバテ状態フラグ（初期値false）を設定
3. 区間1からNまで順番に処理：
   • バテ状態に応じて体力を消費（バテていない: \(D_i\)、バテている: \(2 \times D_i\)）
   • 体力が0以下でバテていない場合、バテ状態フラグをtrueに設定
   • 現在の区間が最後の区間でなければ、対応する回復量を加算
4. 最終的な体力を出力

計算量

• 時間計算量: \(O(N + M)\)
  • 入力読み込みに \(O(N + M)\)
  • メインループに \(O(N)\)
• 空間計算量: \(O(N)\)
  • 難易度配列と回復量配列にそれぞれ \(O(N)\)

実装のポイント

• 回復量は同じ区間に複数の山小屋がある可能性があるため、加算方式で配列に格納

• バテ状態は一度trueになったら変更しない

• 最後の区間（i = N）では回復処理を行わない

• 入力データの読み込みにはイテレータを使用して効率化

  ソースコード

import sys

def main():
    data = sys.stdin.read().split()
    if not data:
        return
    
    it = iter(data)
    N = int(next(it)); M = int(next(it)); S = int(next(it))
    D = [0] * (N+1)
    for i in range(1, N+1):
        D[i] = int(next(it))
    
    recoveries = [0] * (N+1)
    for _ in range(M):
        p = int(next(it)); r = int(next(it))
        recoveries[p] += r
    
    current_health = S
    is_bate = False
    
    for i in range(1, N+1):
        if not is_bate:
            current_health -= D[i]
        else:
            current_health -= 2 * D[i]
            
        if current_health <= 0 and not is_bate:
            is_bate = True
            
        if i < N:
            current_health += recoveries[i]
            
    print(current_health)

if __name__ == "__main__":
    main()

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