概要

各地点までの「最小疲労」を順に求めていく動的計画法（DP）の問題です。
地点 \(i\) へは地点 \(i-1\) または地点 \(i-2\) からしか来られないため、前の状態から最小値を更新していけば解けます。

考察

この問題では、地点 \(1\) から地点 \(N\) まで進むときの疲労の合計を最小にしたいです。

移動できるのは

• 1つ先の地点
• 2つ先の地点

だけなので、各地点に到達する方法は多くても 2 通りしかありません。
この「ある地点の最適解が、その少し前の地点の最適解から決まる」という形は、動的計画法を考える典型パターンです。

重要な観察

地点 \(i\) から地点 \(j\) へ移動するときの疲労は

• \(A_j > A_i\) なら \(A_j - A_i\)
• \(A_j \leq A_i\) なら \(0\)

つまり、式で書くと \( \max(A_j - A_i, 0) \) です。

たとえば標高が

• \(10 \to 15\) なら疲労は \(5\)
• \(15 \to 10\) なら疲労は \(0\)

です。
下りでは疲労が増えないのがポイントです。

素朴な方法ではなぜだめか

地点ごとに「1歩進むか2歩進むか」を全探索すると、経路数は指数的に増えます。
\(N\) は最大で \(5 \times 10^5\) と非常に大きいため、全経路を試す方法は到底間に合いません。

どう解決するか

そこで、各地点までの最小疲労を記録する DP を使います。

\(dp[i]\) を
「地点 \(1\) から地点 \(i+1\) まで到達する最小疲労」
とします（コードに合わせて 0-indexed で管理）。

すると、地点 \(i\) には次の 2 通りで到達できます。

• 地点 \(i-1\) から 1 歩で来る
• 地点 \(i-2\) から 2 歩で来る

したがって、遷移は

$

dp[i]

\min\Bigl( dp[i-1] + \max(Ai - A{i-1}, 0), \; dp[i-2] + \max(Ai - A{i-2}, 0) \Bigr) $

となります（\(i \geq 2\) のとき）。

初期値は、出発地点である地点 \(1\) にいる時点で疲労は \(0\) なので

\( dp[0] = 0 \)

です。

具体例

たとえば \(A = [10, 30, 20, 40]\) のときを考えます。

• \(dp[0] = 0\)
• \(dp[1] = dp[0] + \max(30 - 10, 0) = 20\)
• \(dp[2]\)
  • \(1 \to 2 \to 3\): \(20 + \max(20 - 30, 0) = 20\)
  • \(1 \to 3\): \(0 + \max(20 - 10, 0) = 10\)
  • よって \(dp[2] = 10\)
• \(dp[3]\)
  • \(2 \to 4\): \(20 + \max(40 - 30, 0) = 30\)
  • \(3 \to 4\): \(10 + \max(40 - 20, 0) = 30\)
  • よって \(dp[3] = 30\)

答えは \(30\) です。

アルゴリズム

1. 配列 \(dp\) を用意し、すべて十分大きい値で初期化する。
2. \(dp[0] = 0\) とする。
3. \(i = 1\) から \(N-1\) まで順に、以下を行う。
   • 地点 \(i-1\) から来る場合： \( dp[i] = \min(dp[i],\ dp[i-1] + \max(A_i - A_{i-1}, 0)) \)
   • \(i \geq 2\) なら、地点 \(i-2\) から来る場合： \( dp[i] = \min(dp[i],\ dp[i-2] + \max(A_i - A_{i-2}, 0)) \)
4. 最後に \(dp[N-1]\) を出力する。

計算量

• 時間計算量: \(O(N)\)
• 空間計算量: \(O(N)\)

実装のポイント

• 疲労の増加量は必ず \( \max(A_j - A_i, 0) \) で計算すること。

• 配列は Python では 0-indexed なので、問題文の「地点 \(1\)」はコードでは A[0] に対応します。

• 初期化用の INF は、十分大きければ何でもよいです。コードでは 10**30 を使っています。

• この問題は前 2 状態しか使わないので、理論上は空間を \(O(1)\) に削減できますが、\(O(N)\) でも制約内で十分間に合います。

  ソースコード

import sys

def main():
    input = sys.stdin.readline
    N = int(input())
    A = list(map(int, input().split()))
    
    INF = 10**30
    dp = [INF] * N
    dp[0] = 0
    
    for i in range(1, N):
        dp[i] = min(dp[i], dp[i - 1] + max(A[i] - A[i - 1], 0))
        if i >= 2:
            dp[i] = min(dp[i], dp[i - 2] + max(A[i] - A[i - 2], 0))
    
    print(dp[-1])

if __name__ == "__main__":
    main()

---

この解説は gpt-5.4-high によって生成されました。