概要

\(N\) 段の階段を登る際に消費する体力の合計を求める問題です。基本的には段差の高さと同じ体力を消費しますが、直前の段差よりも高い段差を登る場合は消費体力が 2 倍になるという条件を正しく判定して計算する必要があります。

考察

この問題で重要なのは、「現在の段差と 1 つ前の段差を比較する」という点です。

• 1 段目：常に \(A_1\) の体力を消費します。
• \(i\) 段目（\(i \ge 2\)）：
  • \(A_i > A_{i-1}\) ならば、体力を \(2 \times A_i\) 消費する。
  • そうでない（\(A_i \le A_{i-1}\)）ならば、体力を \(A_i\) 消費する。

制約を確認すると、階段の段数 \(N\) は最大 \(2 \times 10^5\) です。1 段目から順番に前の段と比較しながら計算していくことで、全ての段を 1 回ずつ確認するだけで答えが求められます。

また、各段の高さ \(A_i\) が最大 \(10^9\) であり、それが \(2 \times 10^5\) 個あるため、合計値は最大で \(2 \times 10^9 \times 2 \times 10^5 = 4 \times 10^{14}\) 程度になります。これは一般的な 32 ビット整数型の範囲（約 \(2 \times 10^9\)）を超えるため、プログラミング言語によっては 64 ビット整数型（Python であれば通常の整数型）を使用する必要がある点に注意しましょう。

アルゴリズム

以下の手順で計算を行います。

1. 合計体力を保持する変数 total_stamina を用意し、最初の段差 \(A_1\) で初期化する。
2. \(i = 2\) から \(N\) まで、以下の処理を繰り返す。
   • もし \(A_i > A_{i-1}\) ならば、total_stamina に \(2 \times A_i\) を加算する。
   • そうでなければ、total_stamina に \(A_i\) を加算する。
3. 最終的な total_stamina の値を出力する。

計算量

• 時間計算量: \(O(N)\)
  • 階段の段数 \(N\) に対して、1 回のループで各段を処理するため、計算量は \(N\) に比例します。
• 空間計算量: \(O(N)\)
  • 全ての段差の高さをリスト（配列）に格納する場合、入力サイズに応じたメモリが必要になります。

実装のポイント

• インデックスのずれに注意: プログラミング言語の配列は通常 0 から始まるため、問題文の \(i\) 段目（1-indexed）とコード上のインデックス（0-indexed）がずれないように注意しましょう。

• 最初の段の処理: 1 段目には「直前の段」が存在しないため、ループの外で個別に処理するか、ループの開始位置を工夫することで、範囲外アクセスを防ぐことができます。

  ソースコード

import sys

def main():
    # 入力をすべて読み込み、スペースや改行で分割してリストに格納する
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    # Nは階段の段数
    n = int(input_data[0])
    # aは各段差の高さを格納したリスト
    # a[0]が1段目、a[1]が2段目、...、a[n-1]がn段目に対応する
    a = list(map(int, input_data[1:]))
    
    if n == 0:
        return
    
    # 最初の1段目を登る際に消耗する体力（驚くことはない）
    total_stamina = a[0]
    
    # 2段目から最後の段まで順番に計算する
    for i in range(1, n):
        # 現在の段差が直前の段差よりも真に大きい場合
        if a[i] > a[i-1]:
            # 消耗する体力は2倍になる
            total_stamina += 2 * a[i]
        else:
            # 通常の体力を消耗する
            total_stamina += a[i]
    
    # 合計の消耗体力を出力する
    print(total_stamina)

if __name__ == '__main__':
    main()

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