概要

横一列に並んだ \(N\) 本の花の高さを調整し、どの連続する \(K\) 本の花を見ても「最大の高さ \(-\) 最小の高さ \(\leq D\)」となるようにします。花は切ることしかできない条件のもとで、最終的な花の高さの合計を最大化する問題です。

考察

条件「連続する \(K\) 本の花の高さの最大値と最小値の差が \(D\) 以下」を満たすためには、ある花 \(i\) は、自身と同じ連続する \(K\) 本の区間に含まれる他の花よりも高すぎてはいけません。

具体的には、花 \(i\) の高さは、左側にある \(K-1\) 本の花の中で最も低い花の高さ \(+ D\) 以下でなければなりません。同時に、右側にある \(K-1\) 本の花の中で最も低い花の高さ \(+ D\) 以下でなければなりません。

素朴にすべての区間をチェックしようとすると \(O(NK)\) となり制限時間内に間に合いません。 そこで、以下のように考えます。 1. 左からの制約（配列 \(L\)）: 左から順番に花を見ていき、花 \(i\) に対して過去 \(K-1\) 個の花の \(L\) の値の最小値を \(m\) としたとき、花 \(i\) の高さは \(\min(H_i, m + D)\) に制限されます。 2. 右からの制約（配列 \(R\)）: 右から順番に花を見ていき、花 \(i\) に対して未来 \(K-1\) 個の花の \(R\) の値の最小値を \(m'\) としたとき、花 \(i\) の高さは \(\min(H_i, m' + D)\) に制限されます。

最終的な花 \(i\) の最適な高さは、これら左からの制約と右からの制約を両方満たす必要があるため、\(H'_i = \min(L_i, R_i)\) となります。 各方向について「幅 \(K-1\) のスライド最小値」を求めればよいので、スライド最小値（Monotone Queue）を用いることで \(O(N)\) で計算できます。

アルゴリズム

1. \(K = 1\) のとき、条件を満たす制約がないため、初期状態の合計 \(\sum H_i\) をそのまま出力します。
2. \(K \geq 2\) のとき、Deque（両端キュー）を用いて幅 \(c = K-1\) のスライド最小値を計算します。
3. 左からの伝播:
   • \(i = 0\) から \(N-1\) までループします。
   • キューの先頭が区間 \([i - c, i - 1]\) から外れていれば削除します。
   • キューが空でなければ、最小値 \(m\) を取得し、\(L_i = \min(H_i, m + D)\) とします。空なら \(L_i = H_i\) です。
   • \(L_i\) をキューに追加します。その際、キューの末尾から \(L_i\) 以上の値を削除してから追加することで、キューが単調増加に保たれます。
4. 右からの伝播:
   • \(i = N-1\) から \(0\) まで逆順にループし、同様に \(R_i\) を計算します。
5. 各 \(i\) について \(\min(L_i, R_i)\) を求め、その合計値を出力します。

計算量

• 時間計算量: \(O(N)\)。各要素はDequeへの追加・削除が高々1回ずつ行われるためです。
• 空間計算量: \(O(N)\)。配列 \(H, L, R\) およびDequeのサイズが \(N\) に比例します。

実装のポイント

• Pythonでは標準の collections.deque を使うこともできますが、配列と head, tail ポインタを使ってDequeを模擬すると定数倍が速くなります。

• スライド最小値を保持するキューは、「値そのもの」ではなく「インデックス」を保持することで、範囲外参照のチェックが容易になります。

• 末尾から要素を削除する際、単調性を保つために >= で比較します。

  ソースコード

import sys

def solve():
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    N = int(input_data[0])
    K = int(input_data[1])
    D = int(input_data[2])
    H = list(map(int, input_data[3:3+N]))
    
    if K == 1:
        print(sum(H))
        return
        
    c = K - 1
    
    L = [0] * N
    dq = [0] * N
    head = 0
    tail = 0
    
    for i in range(N):
        while head < tail and dq[head] < i - c:
            head += 1
        
        if head < tail:
            min_val = L[dq[head]]
            val = min_val + D
            L[i] = H[i] if H[i] < val else val
        else:
            L[i] = H[i]
            
        while head < tail and L[dq[tail - 1]] >= L[i]:
            tail -= 1
        dq[tail] = i
        tail += 1
        
    R = [0] * N
    head = 0
    tail = 0
    
    for i in range(N - 1, -1, -1):
        while head < tail and dq[head] > i + c:
            head += 1
            
        if head < tail:
            min_val = R[dq[head]]
            val = min_val + D
            R[i] = H[i] if H[i] < val else val
        else:
            R[i] = H[i]
            
        while head < tail and R[dq[tail - 1]] >= R[i]:
            tail -= 1
        dq[tail] = i
        tail += 1
        
    ans = 0
    for i in range(N):
        l_val = L[i]
        r_val = R[i]
        ans += l_val if l_val < r_val else r_val
        
    print(ans)

if __name__ == '__main__':
    solve()

この解説は or-glm5.2-high によって生成されました。