概要

階段を登る際に、前の段差より高い段差では体力消耗が2倍になるという条件のもと、全段を登り終えたときの総消耗体力を計算する問題です。

考察

この問題で重要な気づきは以下の点です：

1. 1段目は特別扱い: 最初の段は「直前の段差」が存在しないため、必ず通常の体力 \(A_1\) を消耗します。

2. 2段目以降の判定: \(i\) 段目（\(i \geq 2\)）を登るとき、\(A_i > A_{i-1}\) であれば体力消耗が2倍になります。

具体例で考える

例えば、\(N = 4\)、\(A = [3, 5, 2, 4]\) の場合：

合計: \(3 + 10 + 2 + 8 = 23\)

アプローチの検討

この問題は各段を順番に見ていくだけで解けます。\(N\) が最大 \(2 \times 10^5\) であっても、1回のループで処理できるため、素朴なアプローチで十分高速に動作します。特別な工夫は必要ありません。

アルゴリズム

1. 最初の段の消耗体力 \(A_0\) を合計に加える
2. 2段目から \(N\) 段目まで順に以下を繰り返す：
   • 現在の段差 \(A_i\) が直前の段差 \(A_{i-1}\) より大きければ、\(2 \times A_i\) を加算
   • そうでなければ、\(A_i\) を加算
3. 合計を出力

total = A[0]
for i = 1 to N-1:
    if A[i] > A[i-1]:
        total += 2 * A[i]
    else:
        total += A[i]

計算量

• 時間計算量: \(O(N)\)
  • 配列を1回走査するだけ
• 空間計算量: \(O(N)\)
  • 入力配列 \(A\) を保持するため

実装のポイント

• インデックスに注意: 配列は0-indexedなので、「1段目」は A[0]、「\(i\) 段目」は A[i-1] に対応します。コードでは0-indexedのまま処理しています。

• オーバーフローに注意: \(A_i\) が最大 \(10^9\) で \(N\) が最大 \(2 \times 10^5\) のため、最悪ケースでは合計が約 \(4 \times 10^{14}\) 程度になります。Pythonでは整数のオーバーフローを気にする必要はありませんが、C++などでは long long 型を使う必要があります。

• ループの開始位置: 1段目は必ず通常消耗なので、先に処理してからループを2段目（index 1）から開始すると、コードがシンプルになります。

  ソースコード

N = int(input())
A = list(map(int, input().split()))

total = A[0]  # 最初の1段目は驚かない

for i in range(1, N):
    if A[i] > A[i-1]:
        total += 2 * A[i]
    else:
        total += A[i]

print(total)

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