概要

連続区間をまとめて \(1\) ずつ減らせる操作で、配列 \(A\) をすべて \(0\) 以下にするための最小操作回数を求める問題です。結論として、答えは「高さが増えるところの増分の合計」になります。

考察

この操作は「選んだ区間の各要素を一律に \(1\) 減らす」なので、直感的には何度も区間を選んで減らしていくことになります。しかし、毎回区間を探してシミュレーションすると、\(A_i\) が最大 \(10^9\) なので操作回数自体が非常に大きくなり、到底間に合いません（TLE）。

ここで重要な観察は次の通りです。

• ある位置 \(i\) の雪を \(A_i\) 回減らす必要がある。
• ただし減らし方は区間でまとめられるので、隣同士で共通して減らせる部分がある。

これを「層（高さ）ごとに見る」と分かりやすいです。
高さ \(h\)（\(1 \le h \le \max A\)）について、\(A_i \ge h\) となる区画は雪が高さ \(h\) の層を持っています。この層に対しては、連続している部分を 1 回の操作でまとめて削れます。

つまり、

• 各高さ \(h\) ごとに、「\(A_i \ge h\) となる連続区間の個数」が、その高さで必要な操作回数
• 全高さで合計したものが答え

となります。

これをそのまま高さ方向に数えるのは無理ですが、配列方向に見ると簡単に数えられます。
区画 \(i\) に新しく必要になる操作回数は、前より高さが増えた分だけです。

• \(A_1\) は最初の高さなので、その分だけ操作が必要
• \(i \ge 2\) では、もし \(A_i > A_{i-1}\) なら、その増えた分 \(A_i - A_{i-1}\) だけ「新しい層」が始まるので操作回数が増える
• \(A_i \le A_{i-1}\) の場合は、前からの操作でまかなえるので追加は不要

例：\(A = [2, 1, 3, 3, 1]\) - 初期：\(ans = 2\) - \(1-2=-1\) 追加なし - \(3-1=2\) 追加 \(+2\) - \(3-3=0\) 追加なし - \(1-3=-2\) 追加なし
合計 \(2+2=4\)

この 4 回で必ず可能であり、これ未満にはできない（増えた分の層はその地点から新たに削り始める必要がある）ため、最小回数になります。

アルゴリズム

1. \(ans = A_1\) とする（最初の区画の高さ分は必ず必要）。
2. \(i=2\) から \(N\) まで順に見て、差分 \(diff = A_i - A_{i-1}\) を計算する。
3. \(diff > 0\) のときだけ \(ans += diff\) を行う。
4. \(ans\) を出力する。

これは「\(A\) の左から見て、増えた分だけ足す」だけです。式で書くと
\(ans = A_1 + \sum_{i=2}^{N} \max(0, A_i - A_{i-1})\)
です。

計算量

• 時間計算量: \(O(N)\)
• 空間計算量: \(O(N)\)（入力配列を保持するため。保持せず逐次処理なら \(O(1)\) でも可能）

実装のポイント

• \(N \le 2\times 10^5\) なので \(O(N)\) で十分間に合います。

• \(A_i\) は最大 \(10^9\) で答えも大きくなり得ますが、Python の int は多倍長なのでそのままで安全です。

• 入力は sys.stdin.buffer.read() を使うと高速に読めます。

• 本質は「正の差分だけ加算する」ことなので、条件 if diff > 0: ans += diff が核心です。

  ソースコード

import sys

def main():
    it = iter(sys.stdin.buffer.read().split())
    n = int(next(it))
    a = [int(next(it)) for _ in range(n)]

    ans = a[0]
    for i in range(1, n):
        diff = a[i] - a[i - 1]
        if diff > 0:
            ans += diff

    print(ans)

if __name__ == "__main__":
    main()

---

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