概要

連続する区間の雪を1cmずつ減らす操作を繰り返して、すべての区画の雪を0以下にする最小回数を求める問題です。これは「階段の塗り分け」と呼ばれる典型問題に帰着できます。

考察

問題の視覚化

まず、各区画の雪の量を棒グラフとして考えてみましょう。

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

    ■
    ■ 
■   ■   ■
■   ■   ■
■ ■ ■ ■
■ ■ ■ ■
■ ■ ■ ■
─────────
1 2 3 4

重要な気づき

1回の操作で「連続する区間を1cm減らす」というのは、棒グラフで言えば「横一列に連続する部分を1段削る」ことに相当します。

つまり、この問題は 「この棒グラフ全体を、何本の横線（連続する水平線）で覆えるか」 という問題と同じです。

素朴なアプローチの問題点

愚直に「毎回最も効率的な区間を選んで操作する」というシミュレーションを行うと、最大で \(10^9\) 回の操作が必要になり、TLEになってしまいます。

解決の鍵

棒グラフを左から右へ見ていくと： - 高さが増加する部分では、新しい横線を追加で引く必要があります - 高さが減少または同じ部分では、既存の横線を延長（または終了）するだけで済みます

例えば上の例で： - 区画1: 高さ3 → 3本の線が必要 - 区画2: 高さ5（+2増加）→ 2本の線を追加 - 区画3: 高さ2（減少）→ 追加不要 - 区画4: 高さ4（+2増加）→ 2本の線を追加

合計: \(3 + 2 + 0 + 2 = 7\) 回

アルゴリズム

答えは以下の式で計算できます：

\[\text{答え} = A_0 + \sum_{i=1}^{N-1} \max(0, A_i - A_{i-1})\]

つまり： 1. 最初の区画の雪の量 \(A_0\) をまず加える 2. 隣り合う区画で、後ろの区画の方が高い場合、その差分を加える

これは 差分配列の正の部分の和 と等しいです。

具体例での確認

\(A = [3, 5, 2, 4]\) の場合： - \(A_0 = 3\) - \(A_1 - A_0 = 5 - 3 = 2 > 0\) → 加算 - \(A_2 - A_1 = 2 - 5 = -3 < 0\) → 加算しない - \(A_3 - A_2 = 4 - 2 = 2 > 0\) → 加算

答え: \(3 + 2 + 0 + 2 = 7\)

計算量

• 時間計算量: \(O(N)\)（配列を1回走査するだけ）
• 空間計算量: \(O(N)\)（入力配列の保存）

実装のポイント

• \(A_i\) が最大 \(10^9\) で、\(N\) が最大 \(2 \times 10^5\) なので、答えは最大約 \(2 \times 10^{14}\) になる可能性があります。Pythonでは整数のオーバーフローを気にする必要はありませんが、C++などでは long long を使う必要があります。

• 最初の要素 \(A_0\) を忘れずに加えることが重要です。

  ソースコード

def solve():
    N = int(input())
    A = list(map(int, input().split()))
    
    # この問題は「階段の塗り分け」問題と同等です
    # 各区画の雪の量を棒グラフとして考えると、
    # 1回の操作で連続する区間を1cm減らせます
    # 
    # 最小回数は、隣接する区画間で「増加した分」の合計 + 最初の区画の値
    # これは差分配列の正の部分の和に相当します
    
    # A[0] から始めて、A[i] > A[i-1] となる部分で新しい「層」が必要
    # つまり、増加分だけ追加の操作が必要
    
    result = A[0]  # 最初の区画の雪を除去するのに必要な回数
    
    for i in range(1, N):
        if A[i] > A[i-1]:
            result += A[i] - A[i-1]
    
    print(result)

solve()

---

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