概要

道路の各区画の雪の量を0以下にするために必要な最小の雪かき回数を求める問題です。1回の操作では連続する任意の区間の雪を1センチメートル減らせます。

考察

素朴なアプローチとして、先頭から順に雪を減らしていく方法が考えられます。しかし、単純に各区画を個別に処理すると、\(N\)が最大200,000まで大きくなるため非効率です。

重要な観察は、連続する区間に対して操作を行うことです。例えば、区画\(i\)と\(i+1\)の両方に雪がある場合、一度の操作で両方を同時に減らせます。この性質から、操作回数を最小化するには「隣接する区画をまとめて処理する」ことが効率的だと分かります。

具体的には、先頭から順に見ていき、現在の操作でカバーできる高さ（current）と実際の雪の高さ（\(A_i\)）を比較します。\(A_i\)がcurrentより大きい場合、その差だけ追加の操作が必要になります。

アルゴリズム

貪欲法を用いた以下のアルゴリズムです：

1. 初期化: 答えans=0、現在の操作で減らせる高さcurrent=0
2. 各区画i=0からn-1まで順に処理:
   • もしcurrent < \(A_i\)なら、差(\(A_i\) - current)をansに加算
   • currentを\(A_i\)に更新
3. ansを出力

この方法では、連続する区間をまとめて処理する効果を自然に表現できます。currentは「これまでの操作で既に減らされている高さ」を表し、\(A_i\)がcurrentより大きい部分だけ新たな操作が必要であると判断します。

計算量

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

実装のポイント

• 入力の読み込みはsys.stdin.read()で一括処理することで効率化

• 現在の高さを保持する変数currentを適切に更新することが重要

• 隣接する区画間の関係のみを考慮すればよいため、シンプルなループ処理で実現可能

  ソースコード

def main():
    import sys
    data = sys.stdin.read().split()
    n = int(data[0])
    A = list(map(int, data[1:1+n]))
    
    ans = 0
    current = 0
    for i in range(n):
        if current < A[i]:
            ans += A[i] - current
        current = A[i]
        
    print(ans)

if __name__ == "__main__":
    main()

この解説は deepseekv3 によって生成されました。