概要

高橋君が登山中に体力を消費し、バテるかどうかによって消費体力が変わる問題。各区間を通過するたびに体力が減り、バテるとさらに多く減る。山小屋で回復できるが、バテったら回復しても元に戻らない。最終的な残り体力を求めよ。

考察

この問題は、各区間を順番にシミュレーションしていくことで解ける。重要なポイントは以下の通り：

• バテたかどうかの状態管理：一度でも体力が \(0\) 以下になったら、それ以降は倍の消費になる。これはフラグで管理できる。
• 山小屋の位置と回復処理：各区間の通過後に山小屋があるかどうかを効率的に調べたい。リストで持つと毎回探すのに時間がかかるので、辞書（ハッシュマップ）を使うことで高速にアクセスできる。
• オーバーフローや負の体力への対応：体力は負になることもあり、上限がないため、普通に足し引きすればよい。

素朴な方法（例えば毎回山小屋のリストを線形探索）だと、最悪の場合 \(O(N \times M)\) かかり、制約が大きいためTLEしてしまう。これを避けるために、事前に山小屋情報を辞書で持っておくと、各ステップで \(O(1)\) でアクセスできる。

アルゴリズム

1. 入力を読み込み、山小屋情報を pos -> recovery の辞書で保持する。
2. 体力 stamina を初期値 \(S\) で持ち、バテた状態かどうかを示すフラグ tired を False で初期化する。
3. 各区間 \(i = 1, 2, ..., N\) に対して以下を順に行う：
   • 現在の難易度 \(D_i\) を取得。
   • バテていなければ \(D_i\)、バテていれば \(2 \times D_i\) だけ体力を減らす。
   • 減らしたあとで、まだバテておらず体力が \(0\) 以下なら、tired = True にする。
   • 区間 \(i\) の通過直後に山小屋があれば、その回復量を体力に加える。
4. 最終的な体力を出力する。

計算量

• 時間計算量: \(O(N + M)\)
  （入力読み込みと各区間・山小屋の処理がともに線形）
• 空間計算量: \(O(M)\)
  （山小屋情報を辞書で管理するため）

実装のポイント

• 山小屋の位置は1-indexedで入力されるが、区間は0-indexedで処理するので注意が必要（コードでは i+1 で照合している）。

• 入力を高速に読み込むため、sys.stdin.read を使用している。

• バテた判定は 体力消費後 に行うこと（消費してから判定）。

• 山小屋情報はソートされていない可能性があるので、事前に辞書に入れておくと便利。

  ソースコード

import sys
input = sys.stdin.read

def main():
    data = input().split()
    idx = 0
    
    N = int(data[idx])
    idx += 1
    M = int(data[idx])
    idx += 1
    S = int(data[idx])
    idx += 1
    
    D = [int(data[idx + i]) for i in range(N)]
    idx += N
    
    # 山小屋情報を辞書で管理: pos -> recovery
    huts = {}
    for _ in range(M):
        p = int(data[idx])
        idx += 1
        r = int(data[idx])
        idx += 1
        huts[p] = r
    
    stamina = S
    tired = False
    
    for i in range(N):
        d = D[i]
        # 1. 体力消費
        if not tired:
            stamina -= d
        else:
            stamina -= 2 * d
        
        # 2. バテ判定
        if stamina <= 0 and not tired:
            tired = True
        
        # 3. 回復（山小屋）
        # 区間 i+1 を通過した直後（0-indexed では i）に山小屋があれば回復
        if (i + 1) in huts:
            stamina += huts[i + 1]
    
    print(stamina)

if __name__ == "__main__":
    main()

この解説は qwen3-coder-480b によって生成されました。