概要

山道の \(N\) 個の地点を、1つ飛ばしまたは隣接する地点へ進みながら地点 \(1\) から地点 \(N\) まで移動するとき、上り坂で発生する疲労の合計を最小化する問題です。動的計画法（DP）で解くことができます。

考察

問題の整理

• 地点 \(i\) からは地点 \(i+1\) または地点 \(i+2\) に進める
• 上り（\(A_j > A_i\)）のときだけ疲労 \(A_j - A_i\) が加算される
• 下りや平坦な移動では疲労は \(0\)

重要な気づき

各地点に到達したときの最小疲労さえ分かれば、そこから先の遷移を計算できます。これはまさに DP（動的計画法）の典型パターンです。

地点 \(i\) に到達する方法は、地点 \(i-1\) から来るか、地点 \(i-2\) から来るかの高々2通りしかありません。したがって、各地点について定数回の計算で最小疲労を求められます。

具体例

例えば \(A = [10, 30, 15, 40]\)（\(N = 4\)）の場合：

• 地点1: 疲労 \(0\)（出発地）
• 地点2: 地点1から → \(\max(30-10, 0) = 20\)
• 地点3: 地点1から → \(\max(15-10, 0) = 5\)、地点2から → \(20 + \max(15-30, 0) = 20\)。最小は \(5\)
• 地点4: 地点2から → \(20 + \max(40-30, 0) = 30\)、地点3から → \(5 + \max(40-15, 0) = 30\)。最小は \(30\)

1つ飛ばしで深い谷を避けることで、疲労を抑えられる場合があることがポイントです。

アルゴリズム

動的計画法を使います。

1. \(dp[i]\) を「地点 \(1\) から地点 \(i+1\) まで移動するときの疲労の最小値」と定義する（0-indexed）
2. 初期値：\(dp[0] = 0\)（出発地点では疲労 \(0\)）
3. 遷移：各地点 \(i\) について、地点 \(i+1\) と地点 \(i+2\) への移動を考える $\(dp[j] = \min(dp[j],\; dp[i] + \max(A_j - A_i,\; 0))\)\( ただし \)j \in {i+1, i+2}\( かつ \)j < N$
4. 答えは \(dp[N-1]\)

計算量

• 時間計算量: \(O(N)\) — 各地点で高々2つの遷移先を調べるだけ
• 空間計算量: \(O(N)\) — DP 配列のサイズ

実装のポイント

• DP 配列を十分大きな値（\(\infty\)）で初期化し、\(dp[0] = 0\) とするのが定石です。

• 遷移先のインデックスが \(N\) を超えないように範囲チェック（if j < N）を忘れないようにしましょう。

• sys.stdin.buffer.read() を使って入力を一括読み込みすることで、Python でも \(N = 5 \times 10^5\) 程度の入力を高速に処理できます。

• コストの計算 max(A[j] - A[i], 0) は、上りのときだけ標高差を加算し、下りでは \(0\) にするという問題文の条件を簡潔に表現しています。

  ソースコード

import sys

def main():
    input_data = sys.stdin.buffer.read().split()
    N = int(input_data[0])
    A = [int(input_data[i + 1]) for i in range(N)]
    
    INF = float('inf')
    dp = [INF] * N
    dp[0] = 0
    
    for i in range(N):
        if dp[i] == INF:
            continue
        for j in (i + 1, i + 2):
            if j < N:
                cost = max(A[j] - A[i], 0)
                if dp[j] > dp[i] + cost:
                    dp[j] = dp[i] + cost
    
    print(dp[N - 1])

main()

---

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