概要

\(N\) 個の地点を一列に並んだ順に、1つ先または2つ先の地点へ移動を繰り返して進むとき、移動時に発生する「標高差（登りのみ）」の合計を最小化する問題です。

考察

この問題のポイントは、「ある地点に到達するための最小の疲労度は、その直前の状態から決まる」という点です。

地点 \(i\) に到達する方法は、以下の2通りしかありません。 1. 地点 \(i-1\) から 1 ステップで移動する 2. 地点 \(i-2\) から 2 ステップで移動する

地点 \(i\) に到達した時点での疲労の合計を最小にするには、これら2つのルートのうち、それまでの疲労の蓄積と今回の移動で増える疲労の合計が小さい方を選べばよいことになります。

このように、大きな問題を小さな部分問題（各地点への最小疲労度）に分けて順次に解決していく手法は、動的計画法 (DP) が非常に有効です。

アルゴリズム

動的計画法を用いて解きます。

1. DPテーブルの定義: \(dp[i]\) を「地点 \(i\) に到達するまでに必要な疲労の合計の最小値」と定義します。
2. 初期条件:
   • 地点 1：出発点なので \(dp[1] = 0\) です。
   • 地点 2：地点 1 から来るしかないので、\(dp[2] = \max(A_2 - A_1, 0)\) です。
3. 遷移式: 地点 \(i\) (\(3 \leq i \leq N\)) について、以下の2つの値のうち小さい方を \(dp[i]\) とします。
   • 地点 \(i-1\) からの移動: \(dp[i-1] + \max(A_i - A_{i-1}, 0)\)
   • 地点 \(i-2\) からの移動: \(dp[i-2] + \max(A_i - A_{i-2}, 0)\)

これを \(i=3\) から \(N\) まで順番に計算していくことで、最終的な答え \(dp[N]\) を求めることができます。

計算量

• 時間計算量: \(O(N)\) 地点 3 から \(N\) までを 1 回のループで計算するため、地点の数 \(N\) に比例した時間で計算が終わります。\(N = 5 \times 10^5\) という制約下でも十分に高速です。
• 空間計算量: \(O(N)\) 各地点の最小疲労度を記録する配列（DPテーブル）のサイズが \(N\) となります。

実装のポイント

• 標高差の計算: max(A_j - A_i, 0) は、Pythonでは if 文を使っても良いですし、max(0, diff) と書いても同様の計算ができます。

• 大きな入力の処理: \(N\) が大きいため、input() を繰り返すよりも sys.stdin.read().split() を使って一括で読み込む方が実行時間を短縮できます。

• インデックスの対応: 問題文は地点 1 から始まりますが、プログラム内のリストは 0 番目から始まるため、dp[i] が地点 i+1 に対応するように注意して実装します。

  ソースコード

import sys

def solve():
    # 標準入力からすべてのデータを読み込み、空白で分割してリストにする
    # sys.stdin.read().split() は大量の数値を読み込む際に効率的です
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    # 地点の数 N と、各地点の標高 A を取得
    N = int(input_data[0])
    A = list(map(int, input_data[1:]))
    
    # 地点が1つの場合は移動の必要がないため疲労は0（制約上 N >= 2 ですが、念のため）
    if N == 1:
        print(0)
        return
    
    # dp[i] は地点 i+1 に到達するために必要な最小の疲労合計を格納する
    # 0-indexed で管理するため、地点 1 は dp[0], 地点 N は dp[N-1] に対応
    dp = [0] * N
    
    # 初期条件
    # 地点 1 (dp[0]) の疲労は 0
    dp[0] = 0
    
    # 地点 2 (dp[1]) へは地点 1 からのみ到達可能
    diff_0_1 = A[1] - A[0]
    dp[1] = diff_0_1 if diff_0_1 > 0 else 0
    
    # 地点 3 以降の最小疲労を動的計画法で求める
    for i in range(2, N):
        # 地点 i-1 から移動する場合の疲労
        # 移動先 A[i] が現在地 A[i-1] より高い場合のみその差が加算される
        diff1 = A[i] - A[i-1]
        cost1 = dp[i-1] + (diff1 if diff1 > 0 else 0)
        
        # 地点 i-2 から移動する場合の疲労
        # 移動先 A[i] が現在地 A[i-2] より高い場合のみその差が加算される
        diff2 = A[i] - A[i-2]
        cost2 = dp[i-2] + (diff2 if diff2 > 0 else 0)
        
        # 2つの移動経路のうち、疲労が小さくなる方を選択
        if cost1 < cost2:
            dp[i] = cost1
        else:
            dp[i] = cost2
            
    # 地点 N (dp[N-1]) に到達したときの最小疲労を出力
    print(dp[N-1])

if __name__ == '__main__':
    solve()

---

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