概要

各段差を登るたびに消耗する体力を足し上げます。ただし「直前の段差より今回の段差の方が真に大きい」場合だけ、その段の消耗が \(2\) 倍になるので、その条件を順に判定して合計を求めます。

考察

重要なのは、\(i\) 段目で消耗する体力が「\(A_i\) と \(A_{i-1}\) の大小関係だけ」で決まる点です。
つまり、全体を見渡して複雑な最適化をする必要はなく、左から順に見ていけば確定していきます。

• 通常は \(A_i\) 消耗
• ただし \(A_i > A_{i-1}\) のときだけ \(2A_i\) 消耗
• 1 段目は比較対象がないので必ず \(A_1\)

例えば \(A = [3, 2, 5, 5]\) のとき、 - 1段目: \(3\) - 2段目: \(2\)（\(2 \le 3\)） - 3段目: \(10\)（\(5 > 2\) なので2倍） - 4段目: \(5\)（\(5 \not> 5\)） 合計は \(3+2+10+5=20\) です。

素朴に「驚く回数」などを別に数えたり、不要にデータ構造を使う必要はありません。各段での加算値をその場で決めて足すだけで十分で、これなら \(N \le 2\times 10^5\) でも余裕で間に合います。

アルゴリズム

1. 合計 total を \(A_1\) で初期化する（1段目は必ず通常消耗）。
2. \(i=2..N\) について順に処理する（0-indexなら \(i=1..N-1\)）。
   • もし \(A_i > A_{i-1}\) なら total += 2*A_i
   • そうでなければ total += A_i
3. total を出力する。

計算量

• 時間計算量: \(O(N)\)（各段を1回ずつ比較して足すだけ）
• 空間計算量: \(O(1)\)（入力配列を除けば追加領域は定数）

実装のポイント

• 「真に大きい」なので条件は \(A_i > A_{i-1}\)（\(=\) の場合は2倍にならない）に注意します。

• 合計は最大でおよそ \(2 \times 10^9 \times 2 \times 10^5 = 4 \times 10^{14}\) 程度になり得ますが、Python の int は任意精度なのでそのままで問題ありません。

• 入力が大きいので sys.stdin.readline を使うと安全です。

  ソースコード

import sys

def main():
    input = sys.stdin.readline
    N = int(input().strip())
    A = list(map(int, input().split()))
    total = A[0]
    for i in range(1, N):
        if A[i] > A[i - 1]:
            total += 2 * A[i]
        else:
            total += A[i]
    print(total)

if __name__ == "__main__":
    main()

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