E - 花壇の手入れ / Garden Maintenance Editorial by admin
gemini-3.5-flash-high概要
この問題は、長さ \(N\) の数列 \(H\) に対し、「任意の長さ \(K\) の連続する区間において、最大値と最小値の差が \(D\) 以下」という条件を満たしつつ、各要素を元の値以下に引き下げて得られる数列 \(H'\) の総和を最大化する問題です。
考察
1. 条件の言い換え
「任意の長さ \(K\) の区間において、最大値と最小値の差が \(D\) 以下」という条件を考えます。 区間内の任意の2つの要素のインデックスを \(i, j\) とすると、それらの距離は高々 \(K-1\) です。したがって、この条件は以下のように言い換えることができます。 * \(L = K - 1\) としたとき、任意の \(i, j\) について \(|i - j| \leq L \implies |H'_i - H'_j| \leq D\)
さらに、これは「すべての \(i, j\) について \(|i - j| \leq L \implies H'_i \leq H'_j + D\)」と同値です。
2. 各要素の最大値の定式化
元の高さの制約 \(H'_i \leq H_i\) と、上記の差の制約を同時に満たしつつ、各 \(H'_i\) をできるだけ大きくしたいです。 ある要素 \(j\) の高さが \(H_j\) であるとき、そこから距離 \(L\) 離れるごとに許容される高さは \(D\) ずつ増加します。したがって、すべての \(j\) からの制約を考慮すると、最終的な高さ \(H'_i\) は次のように決まります。
\[H'_i = \min_{1 \leq j \leq N} \left( H_j + \lceil \frac{|i - j|}{L} \rceil D \right)\]
（ただし \(i = j\) のときは \(H_i\) とします）
この式をすべての \(i\) について愚直に計算すると \(O(N^2)\) かかり、 \(N \leq 2 \times 10^5\) の制約下では実行時間制限に間に合いません（TLE）。
3. 左右からの寄与への分解と高速化
計算を高速化するために、自分より左側にある要素（ \(j < i\) ）からの制約 \(f[i]\) と、右側にある要素（ \(j > i\) ）からの制約 \(g[i]\) に分解します。
\[H'_i = \min(H_i, f[i], g[i])\]
ここで、左側からの制約 \(f[i]\) は以下のように定義されます。 $\(f[i] = \min_{j < i} \left( H_j + \lceil \frac{i - j}{L} \rceil D \right)\)$
この式を、直近の \(L\) 個の要素（ \(\lceil \frac{i-j}{L} \rceil = 1\) となる範囲）と、それより左側にある要素に分割してみます。 $\(f[i] = \min \left( \min_{i-L \leq j < i} (H_j + D), \min_{j < i-L} (H_j + \lceil \frac{i - j}{L} \rceil D) \right)\)$
ここで、 \(j < i-L\) のとき \(\lceil \frac{i-j}{L} \rceil = \lceil \frac{i-L-j}{L} \rceil + 1\) が成り立つため、以下のように整理できます。 $\(f[i] = \min \left( \min_{i-L \leq j < i} H_j, \min_{j < i-L} (H_j + \lceil \frac{i-L-j}{L} \rceil D) \right) + D\)$
右側の項はまさに \(f[i-L]\) そのものです。したがって、次のシンプルな漸化式が得られます。 $\(f[i] = \min \left( \min_{i-L \leq j < i} H_j, f[i-L] \right) + D\)$
ここで \(M[i] = \min_{i-L \leq j < i} H_j\) とおくと、 $\(f[i] = \min(M[i], f[i-L]) + D\)$ と表せます。
\(M[i]\) は「スライド最小値（Sliding Window Minimum）」のアルゴリズムを用いることで、全体で \(O(N)\) で計算可能です。これを利用すれば、すべての \(i\) に対する \(f[i]\) を \(O(N)\) で求めることができます。
右側からの制約 \(g[i]\) についても、配列 \(H\) を左右反転させて同じ処理を適用することで、同様に \(O(N)\) で求めることができます。
アルゴリズム
- コーナーケースの処理: \(K = 1\) のときは、高さの差に関する制約が実質的に存在しないため、元の高さの総和 \(\sum H_i\) をそのまま出力します。
- スライド最小値の計算:
両端キュー（
deque）を用いて、各 \(i\) について直近 \(L = K - 1\) 個の要素の最小値 \(M[i]\) を求めます。 - 左側からの制約 \(f\) の計算: 漸化式 \(f[i] = \min(M[i], f[i-L]) + D\) を用いて、左から順に \(f[i]\) を決定します。
- 右側からの制約 \(g\) の計算: 配列 \(H\) を反転させたものに対して同様の処理を行い、得られた結果を再度反転させることで \(g[i]\) を得ます。
- 答えの集計: 各 \(i\) について \(\min(H_i, f[i], g[i])\) を計算し、その総和を出力します。
計算量
- 時間計算量: \(O(N)\)
スライド最小値の計算において、各要素は
dequeに高々1回追加され、高々1回取り出されるため、全体で \(O(N)\) 時間で動作します。漸化式の計算や配列の反転も \(O(N)\) で行えるため、全体の時間計算量は \(O(N)\) となり、実行時間制限に十分間に合います。 - 空間計算量: \(O(N)\)
元の配列 \(H\) のほかに、制約を記録する配列 \(f, g\) や
dequeを保持するために \(O(N)\) のメモリを使用します。
実装のポイント
配列の反転によるコードの共通化: 右側からの制約 \(g\) を求める際、新しく処理を書くのではなく、入力配列を反転（
H[::-1]）させて同じ関数get_fに通し、得られた結果をさらに反転（g_rev[::-1]）させることで、実装をシンプルに保ち、バグの混入を防いでいます。インデックスの境界条件: \(i - L < 0\) となる場合は、前のステップ（ \(f[i-L]\) ）が存在しないため、
INF（十分大きな値）として処理します。ソースコード
import sys
from collections import deque
def solve():
input = sys.stdin.read
data = input().split()
if not data:
return
N = int(data[0])
K = int(data[1])
D = int(data[2])
H = [int(x) for x in data[3:]]
if K == 1:
print(sum(H))
return
L = K - 1
INF = 10**18
def get_f(A):
M = [INF] * N
q = deque()
for i in range(N):
if i > 0:
val = A[i-1]
while q and A[q[-1]] >= val:
q.pop()
q.append(i-1)
if q and q[0] < i - L:
q.popleft()
if q:
M[i] = A[q[0]]
f = [INF] * N
for i in range(1, N):
prev_val = f[i-L] if i-L >= 0 else INF
cand = M[i] if M[i] < prev_val else prev_val
f[i] = cand + D
return f
f = get_f(H)
H_rev = H[::-1]
g_rev = get_f(H_rev)
g = g_rev[::-1]
ans = 0
for i in range(N):
val = H[i]
if f[i] < val:
val = f[i]
if g[i] < val:
val = g[i]
ans += val
print(ans)
if __name__ == '__main__':
solve()
この解説は gemini-3.5-flash-high によって生成されました。
posted:
last update: