概要

連続区間に含まれる雪を同時に減らせる操作を用いて、すべての雪を除去する最小回数を求める問題。

考察

この問題では、1回の操作で連続した区間の雪を1cmずつ減らすことができるので、単純に各区画の雪の量の和を取るのではなく、「どの範囲を何回操作するか」を工夫する必要があります。

たとえば、以下のような入力を考えてみましょう：

\[ N = 5,\quad A = [1, 2, 3, 2, 1] \]

素朴な考えでは、各 \(A_i\) の値だけ操作が必要そうですが、実は連続して操作を行うことで効率よく処理できます。

ここで重要なのは、「増加分」に注目することです。つまり、隣接する要素同士の差 \(A_i - A_{i-1}\) を考えます。これは、前から順番に操作を行う際に新たに必要な操作の回数と捉えることができます。

具体的には、配列 \(A\) の先頭から見て、ある地点で雪の高さが増加している場合、その増加分だけ新たな操作が必要になります。逆に減少している場合は、すでに選んだ区間の操作でカバーできる可能性があります。

そこで、次のような 差分配列 を考えます：

• \(diff[0] = A[0]\)
• \(diff[i] = A[i] - A[i-1]\ (1 \leq i < N)\)
• \(diff[N] = -A[N-1]\) （最後に0まで落とすため）

このとき、正の \(diff[i]\) の合計が、必要な最小操作回数になります。なぜなら、正の増加があるということは、その分だけ新しい「層」を掘り起こす必要があるからです。

例えば、上の例で差分を計算すると：

• \(diff = [1, 1, 1, -1, -1, -1]\)

正の要素の合計は \(1 + 1 + 1 = 3\) となり、これが答えになります。

この方法によって、全要素について個別に操作しなくても、全体の「山の形」に着目することで効率的に操作回数を求めることができます。

アルゴリズム

1. 入力された配列 \(A\) から、隣接要素の差分を計算する。
2. 最初の要素 \(A[0]\) を差分の最初の要素とする。
3. 各 \(i = 1\) から \(N-1\) に対して \(diff[i] = A[i] - A[i-1]\) を計算する。
4. 最後に \(diff[N] = -A[N-1]\) を追加して終端を考慮する。
5. 差分のうち、正の値の合計を取る。それが求める最小操作回数である。

計算量

• 時間計算量: \(O(N)\)
• 空間計算量: \(O(N)\)

実装のポイント

• 差分配列の末尾に \(-A[N-1]\) を追加することを忘れないこと。
• 正の差分のみを合計するときに max(0, d) を使うとシンプルに記述できる。
• 入力を高速に読み込むことで大きな制約にも対応できる（sys.stdin.read を使用）。

## ソースコード

```python
import sys
input = sys.stdin.read

def main():
    data = input().split()
    N = int(data[0])
    A = list(map(int, data[1:]))

    # 差分を計算する（A[-1] = 0 として扱う）
    diff = [A[0]]
    for i in range(1, N):
        diff.append(A[i] - A[i-1])
    
    # 最後に0を追加して終端を考慮
    diff.append(-A[-1])

    # 正の差分の合計が答え
    ans = sum(max(0, d) for d in diff)
    print(ans)

if __name__ == "__main__":
    main()

---

この解説は qwen3-coder-480b によって生成されました。