概要

高橋君が \(N\) 個の区間を順番に通過しながら、山頂を目指すシミュレーション問題です。各区間での体力の消費、バテ状態への変化、山小屋での回復という一連の処理を、ルールに従って正しく実行し、最終的な体力を求めます。

考察

この問題のポイントは、「バテた状態」への変化条件と、その後の影響を正確にシミュレーションすることです。

1. 状態の変化と不可逆性

高橋君の状態は「バテていない」から「バテた」への一方通行です。一度バテると、その後の山小屋で体力がどれだけ回復しても、消費体力が \(2 \times D_i\) になるペナルティは解除されません。

2. 処理の順序

各区間 \(i\) で行われる 3 つの手順の順序が非常に重要です。 1. 消費: 現在の状態に基づいて体力を減らす。 2. 判定: 消費後の体力が \(0\) 以下ならバテ状態にする。 3. 回復: 山小屋があれば回復する。

特に、「消費した直後に \(0\) 以下になったが、その後の回復で正に戻った」という場合でも、手順 2 の時点でバテ判定が行われるため、高橋君はバテた状態になります。 この順序を間違えると正しい結果が得られません。

3. 山小屋の管理

山小屋の情報 \((P_j, R_j)\) は、区間番号 \(P_j\) をキーとして効率的に参照する必要があります。\(N\) のサイズが最大 \(2 \times 10^5\) であるため、各区間の処理中に山小屋リストを全探索すると \(O(N \times M)\) となり、実行時間制限に間に合いません。配列や連想配列（辞書）を使って、特定の区間の後に山小屋があるかどうかを \(O(1)\) で判定できるように準備しておきます。

アルゴリズム

以下の手順でシミュレーションを行います。

1. 準備:
   • 各区間の難易度を配列 \(D\) に格納する。
   • 長さ \(N+1\) の配列 huts を用意し、huts[P_j] = R_j として山小屋の回復量を記録しておく（山小屋がない場所は \(0\)）。
2. 初期化:
   • stamina = S
   • is_tired = False
3. シミュレーション:
   • \(i = 1\) から \(N\) まで順に繰り返す：
     • 消費: is_tired が真なら stamina -= 2 * D[i]、偽なら stamina -= D[i]。
     • 判定: is_tired が偽 かつ stamina <= 0 なら、is_tired = True に更新。
     • 回復: stamina += huts[i]。
4. 出力:
   • 最終的な stamina を出力する。

計算量

• 時間計算量: \(O(N + M)\)
  • 入力の読み込みと山小屋データの格納に \(O(N + M)\) かかります。
  • \(N\) 個の区間を 1 回ずつループで処理するため、シミュレーション部分は \(O(N)\) です。
• 空間計算量: \(O(N)\)
  • 区間の難易度 \(D\) と山小屋の回復量 huts を保持するために \(O(N)\) のメモリを使用します。

実装のポイント

• 大きな数値の扱い: 体力や難易度は最大 \(10^9\) であり、最終的な体力が非常に大きな負の値になったり、初期体力を大きく超えたりする可能性があります。Python では整数の大きさに制限がないため問題ありませんが、他の言語（C++ や Java など）を使用する場合は、64bit 整数型（long long や long）を使用する必要があります。

• 入出力の高速化: \(N\) や \(M\) が大きいため、Python では sys.stdin.read().split() などを用いて一括で入力を読み込むと実行時間を短縮できます。

  ソースコード

import sys

def solve():
    # Read all input at once and convert to integers for efficiency
    try:
        data = list(map(int, sys.stdin.read().split()))
    except EOFError:
        return
    
    if not data:
        return
    
    # N: number of segments, M: number of mountain huts, S: initial stamina
    N = data[0]
    M = data[1]
    S = data[2]
    
    # D: list of difficulties for each segment (D_1 to D_N)
    # They are located from index 3 to 3 + N - 1 in the data list.
    D = data[3 : 3 + N]
    
    # huts: recovery amount at the end of each segment
    # huts[i] stores the recovery amount R_j if a hut is located after segment i (P_j = i).
    # Since P_j is between 1 and N-1, a list of size N+1 is sufficient.
    huts = [0] * (N + 1)
    
    # Offset where the hut information (P_j, R_j) begins
    offset = 3 + N
    for i in range(M):
        p = data[offset + 2 * i]
        r = data[offset + 2 * i + 1]
        huts[p] = r
        
    stamina = S
    is_tired = False
    
    # Simulate the process for each segment from 1 to N
    for i in range(1, N + 1):
        # difficulty of the current segment
        d = D[i - 1]
        
        # 1. Stamina consumption
        if is_tired:
            # If already tired, stamina consumption is doubled
            stamina -= 2 * d
        else:
            # If not tired, stamina consumption is normal
            stamina -= d
            
            # 2. Fatigue check
            # If stamina becomes 0 or less after consumption, the state changes to tired.
            if stamina <= 0:
                is_tired = True
        
        # 3. Recovery at mountain hut (if any)
        # Recovery occurs after the segment is passed and fatigue check is completed.
        stamina += huts[i]
        
    # Output the final remaining stamina
    print(stamina)

if __name__ == "__main__":
    solve()

---

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