概要

麓から山頂まで \(N\) 個の区間を順に通過する登山シミュレーションです。体力が \(0\) 以下になると「バテた状態」になり、以降の体力消費が \(2\) 倍になるという仕組みのもとで、最終的な残り体力を求めます。

考察

この問題は、複雑なアルゴリズムを必要としないシミュレーション問題です。問題文に記載されたルールをそのまま正確に実装すれば正解が得られます。

重要な観察ポイントは以下の通りです：

• バテ状態は不可逆：一度バテた状態になると、体力が回復しても元に戻りません。したがって、状態は「バテていない → バテた」の一方向のみです。
• 処理の順序が大切：各区間では「①体力消費 → ②バテ判定 → ③山小屋回復」の順に処理が行われます。この順序を間違えると不正解になります。
• バテ判定は消費直後、回復前：山小屋の回復は②の後に行われるため、体力消費で \(0\) 以下になったらバテ判定が先に行われ、その後に回復が適用されます。

例えば、体力 \(5\) で難易度 \(6\) の区間を通過すると、体力は \(5 - 6 = -1\) となり \(0\) 以下なのでバテた状態になります。その後、山小屋で \(10\) 回復して体力 \(9\) になっても、バテた状態は解除されません。次の区間からは消費が \(2\) 倍になります。

\(N \leq 2 \times 10^5\) なので、各区間を \(1\) つずつ処理する \(O(N)\) のシミュレーションで十分間に合います。

アルゴリズム

1. 山小屋の情報を配列 recover に格納する。recover[i] は区間 \(i\) の通過直後に得られる回復量（山小屋がなければ \(0\)）。
2. 体力 stamina を初期値 \(S\)、状態 exhausted を False（バテていない）に初期化する。
3. 区間 \(1\) から \(N\) まで順に以下を行う：
   • 体力消費：バテていなければ \(D_i\) を、バテていれば \(2 \times D_i\) を体力から引く。
   • バテ判定：体力が \(0\) 以下かつバテていなければ、バテた状態にする。
   • 山小屋回復：recover[i] が \(0\) より大きければ、体力に加算する。
4. 最終的な体力を出力する。

計算量

• 時間計算量: \(O(N + M)\)
  • 山小屋の情報の読み込みに \(O(M)\)、区間のシミュレーションに \(O(N)\)。
• 空間計算量: \(O(N)\)
  • 難易度配列 \(D\) と回復量配列 recover にそれぞれ \(O(N)\)。

実装のポイント

• 山小屋の配列化：山小屋の情報は \((P_j, R_j)\) の組で与えられ、順序も不定なので、サイズ \(N+1\) の配列を用意して recover[P_j] = R_j と格納すると、シミュレーション中に \(O(1)\) で参照できます。

• 体力の範囲に注意：\(S\) や \(D_i\)、\(R_j\) が最大 \(10^9\) なので、体力は非常に大きな負の値や正の値を取り得ます。Python は多倍長整数を扱えるのでオーバーフローの心配はありませんが、C++ などでは long long を使う必要があります。

• 入力の高速化：\(N\) が最大 \(2 \times 10^5\) のため、Python では sys.stdin.buffer.read() でまとめて読み込むことで入力を高速化しています。

  ソースコード

import sys

def main():
    input_data = sys.stdin.buffer.read().split()
    idx = 0
    N = int(input_data[idx]); idx += 1
    M = int(input_data[idx]); idx += 1
    S = int(input_data[idx]); idx += 1
    
    D = [int(input_data[idx + i]) for i in range(N)]
    idx += N
    
    recover = [0] * (N + 1)  # recover[i] = recovery after section i
    for j in range(M):
        P = int(input_data[idx]); idx += 1
        R = int(input_data[idx]); idx += 1
        recover[P] = R
    
    stamina = S
    exhausted = False
    
    for i in range(1, N + 1):
        # Step 1: consume stamina
        if not exhausted:
            stamina -= D[i - 1]
        else:
            stamina -= 2 * D[i - 1]
        
        # Step 2: check if becomes exhausted
        if stamina <= 0 and not exhausted:
            exhausted = True
        
        # Step 3: mountain hut recovery
        if recover[i] > 0:
            stamina += recover[i]
    
    print(stamina)

main()

この解説は claude4.6opus-thinking によって生成されました。