概要

この問題は、与えられた \(N\) 個の区画の雪の量を、最小限の「区間に対する減算操作」ですべて \(0\) にする問題です。 これは競技プログラミングでは典型的な問題の一つで、隣り合う要素の差分に着目することで効率よく解くことができます。

考察

まず、具体的な例で考えてみましょう。雪の量が [1, 3, 2] という状態を考えます。

1. 1番目の区画（量: 1）: 前の区画（\(0\) とみなす）よりも雪が \(1\) 増えています。この \(1\) センチを消すためには、少なくとも \(1\) 回の雪かきが必要です。
2. 2番目の区画（量: 3）: 前の区画（量: 1）よりもさらに雪が \(2\) センチ多いです。前の区画と一緒に雪かきをしても \(1\) センチ分しか減らせないため、この区画のために追加で \(2\) 回の雪かきを新しく開始する必要があります。
3. 3番目の区画（量: 2）: 前の区画（量: 3）よりも雪が少ないです。この区画の雪は、2番目の区画で行った雪かきのついでに処理することができるため、新しく雪かきを始める必要はありません。

このように、「前の区画よりも雪の量が増えた分だけ、新しい雪かき操作を開始しなければならない」ということに気づくのがポイントです。

逆に、前の区画より雪が減っている場合は、前の区画で行っていた雪かき操作のいくつかをその手前で終了させればよいため、追加の回数は発生しません。

アルゴリズム

この問題は、以下の手順で解くことができます。

1. 答えを保持する変数 ans を \(0\)、直前の区画の雪の量を保持する変数 prev_snow を \(0\) とします。
2. 各区画の雪の量 \(A_i\) を左から順番に見ていきます。
3. もし現在の雪の量 \(A_i\) が prev_snow よりも大きい場合、その差分（\(A_i - prev\_snow\)）を ans に加算します。
4. prev_snow を現在の \(A_i\) で更新します。
5. 全ての区画を見終わった後の ans が最小回数となります。

この手法は、各要素を一度ずつ確認するだけで済むため、非常に高速です。

計算量

• 時間計算量: \(O(N)\)
  • \(N\) 個の要素を一度ずつ走査するため、入力の大きさに比例した時間で計算が終わります。
• 空間計算量: \(O(N)\)
  • 入力値をリストとして保持する場合に \(O(N)\) のメモリを使用します。

実装のポイント

• 大きな入力への対応: \(N\) が最大 \(2 \times 10^5\) と大きいため、Pythonでは sys.stdin.read().split() などを使って一括で入力を読み込むと実行時間を短縮できます。

• 差分の計算: 最初の要素 \(A_1\) についても「\(0\) から \(A_1\) に増えた」と考えることで、ループの中で統一的に処理できます。

• 数値の大きさ: 雪の量 \(A_i\) は最大 \(10^9\) に達するため、合計値が \(32\) ビット整数を超えてしまう可能性があります。Pythonでは自動的に多倍長整数として扱われるため問題ありませんが、他の言語（C++など）では long long 型などを使用する必要があります。

  ソースコード

import sys

def main():
    # Read all input data at once and split into tokens
    # Using sys.stdin.read().split() is efficient for the given constraints
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    # The first token is N, the number of sections
    n = int(input_data[0])
    
    # The following tokens are the snow amounts A_1, A_2, ..., A_N
    # The problem asks for the minimum number of range-decrement operations
    # to make all snow amounts 0 or less. In the context of "snow shoveling"
    # problems, this typically implies that you can only shovel sections
    # where snow actually exists (A_i > 0). This is a classic problem
    # equivalent to AtCoder Beginner Contest 116 C - Grand Garden.
    # The minimum number of operations is the sum of positive differences
    # between adjacent sections: sum(max(0, A_i - A_{i-1})) where A_0 = 0.
    
    ans = 0
    prev_snow = 0
    
    # Iterate through each section's snow amount
    # input_data[1] is A_1, input_data[2] is A_2, ..., input_data[n] is A_n
    for i in range(1, n + 1):
        current_snow = int(input_data[i])
        # If the current section has more snow than the previous one,
        # we must start at least (current_snow - prev_snow) new operations
        # that cover this section but did not cover the previous one.
        if current_snow > prev_snow:
            ans += (current_snow - prev_snow)
        prev_snow = current_snow
    
    # Output the total minimum number of operations
    print(ans)

if __name__ == '__main__':
    main()

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