E - 山型整地 / Mountain-Shaped Leveling 解説 by admin
gemini-3.5-flash-high概要
この問題は、与えられた土地の高さの列 \(H\) に対し、「区間の高さを \(1\) 減らす」という操作を繰り返して、山型の列 \(H'\) にするための最小操作回数を求める問題です。
一見複雑な操作に見えますが、隣接する要素の「差分」と「累積和」に着目することで、山頂（ピーク）となる位置 \(k\) を全探索し、各 \(k\) に対する最小コストを \(O(1)\) で計算できるようになります。全体として \(O(N)\) の時間計算量で解くことができます。
考察
1. 操作の言い換えと「隣接差分」への注目
「区間 \([l, r]\) の高さを \(1\) 減らす」という操作を、隣接する要素の差分 \(D_i = H_i - H_{i-1}\) （ただし \(H_0 = H_{N+1} = 0\) とします）の視点で考えてみましょう。 この操作を行うと、差分は以下のように変化します。 - \(D_l\) が \(1\) 減少する - \(D_{r+1}\) が \(1\) 増加する - その他の \(D_i\) は変化しない
この性質から、数列 \(H\) をすべて \(0\) にするために必要な最小操作回数は、隣接差が正である部分の総和 \(\sum \max(0, D_i)\) に一致することが知られています。 （同様に、隣接差が負である部分の絶対値の総和とも一致します。初期状態と最終状態がともに \(0\) であるため、増加分と減少分の総和は等しくなります）。
2. 山型にするための条件
目標は、操作後の列 \(H'\) を \(k\) 番目の区画をピークとする山型にすることです。山型であるとは、以下の条件を満たすことです。 - 左側（\(1 \le i \le k\)）: 広義単調非減少。すなわち、隣接差がすべて \(0\) 以上（減少がない：\(D'_i \ge 0\)）。 - 右側（\(k+1 \le i \le N+1\)）: 広義単調非増加。すなわち、隣接差がすべて \(0\) 以下（増加がない：\(D'_i \le 0\)）。
元々の列 \(H\) から高さを「減らす」ことしかできないため、山型を達成するためには、山型に反している部分を削る必要があります。
左側（\(1 \le i \le k\)）のコスト: 左側を単調非減少にするためには、元々の \(H\) の左側にある「減少している部分（\(D_i < 0\)）」をすべて解消しなければなりません。 これを解消するために必要な最小の削り量は、左側の減少分の絶対値の総和になります。 $\(SM[k] = \sum_{i=1}^k \max(0, -D_i)\)$
右側（\(k+1 \le i \le N+1\)）のコスト: 右側を単調非増加にするためには、元々の \(H\) の右側にある「増加している部分（\(D_i > 0\)）」をすべて解消しなければなりません。 これを解消するために必要な最小の削り量は、右側の増加分の総和になります。 $\(SP[N+1] - SP[k] \quad \left(ただし、SP[x] = \sum_{i=1}^x \max(0, D_i)\right)\)$
3. 最小コストの計算
左右の操作は独立に行うことができるため、ある位置 \(k\) をピークとしたときに山型にするための最小操作回数 \(\text{Cost}(k)\) は、単に左右のコストの和になります。 $\(\text{Cost}(k) = SM[k] + (SP[N+1] - SP[k])\)$
ここで、 - \(SP[i]\) : \(1\) から \(i\) 番目までの隣接差の正の部分の累積和 - \(SM[i]\) : \(1\) から \(i\) 番目までの隣接差の負の部分の絶対値の累積和 - \(SP[N+1]\) : 数列全体で隣接差が正の部分の総和（＝すべてを \(0\) にする総コスト）
この \(\text{Cost}(k)\) をすべての \(k\) （\(0 \le k \le N\)）について計算し、その最小値が求める答えとなります。累積和を事前に計算しておくことで、各 \(k\) に対するコストは \(O(1)\) で求められます。
アルゴリズム
- 番兵の追加: 配列 \(H\) の先頭と末尾に \(0\) を追加し、 \(H_0 = 0, H_{N+1} = 0\) とします。これにより、端の処理を統一的に行えます。
- 累積和の構築:
隣接差 \(D_i = H_i - H_{i-1}\) を順に計算し、以下の2つの累積和配列を構築します。
- \(SP[i]\): \(D_i > 0\) のときの \(D_i\) の累積和
- \(SM[i]\): \(D_i < 0\) のときの \(|D_i|\) の累積和
- 最小値の探索: \(k = 0\) から \(N\) までの各位置について、 \(\text{Cost}(k) = SM[k] + SP[N+1] - SP[k]\) を計算し、その最小値を求めます。
計算量
- 時間計算量: \(O(N)\) 累積和の構築に \(O(N)\)、各 \(k\) についての最小値探索に \(O(N)\) かかるため、全体で \(O(N)\) となり、制約の \(N = 10^6\) に対しても高速に動作します。
- 空間計算量: \(O(N)\) 累積和配列 \(SP, SM\) を保持するために \(O(N)\) のメモリを使用します。
実装のポイント
高速な入出力: Pythonでは入力数が \(10^6\) 規模になると
input()では間に合わない可能性があるため、sys.stdin.read().split()を用いて一括で入力を取得しています。コードにおける
Ukの計算について: 提示されたコード内の以下の部分：val1 = SM[k] val2 = SP[k] - H[k] Uk = val1 if val1 > val2 else val2数学的には \(H_k = SP[k] - SM[k]\) が成り立つため、 \(SP[k] - H[k] = SM[k]\) となり、
val1とval2は常に等しくなります。したがって、Ukは常にSM[k]となり、コストの式はSM[k] + sp_total - SP[k]とシンプルに表せます。ソースコード
import sys
def solve():
# Fast I/O
input_data = sys.stdin.read().split()
if not input_data:
return
N = int(input_data[0])
H = [0] + [int(x) for x in input_data[1 : N + 1]] + [0]
SP = [0] * (N + 2)
SM = [0] * (N + 2)
sp_acc = 0
sm_acc = 0
prev_H = 0
# Compute prefix sums of positive and negative differences
for i in range(1, N + 2):
curr_H = H[i]
diff = curr_H - prev_H
if diff > 0:
sp_acc += diff
else:
sm_acc -= diff
SP[i] = sp_acc
SM[i] = sm_acc
prev_H = curr_H
ans = 10**18
sp_total = SP[N + 1]
# Find the peak k that minimizes the cost
for k in range(0, N + 1):
val1 = SM[k]
val2 = SP[k] - H[k]
Uk = val1 if val1 > val2 else val2
cost = Uk + sp_total - SP[k]
if cost < ans:
ans = cost
print(ans)
if __name__ == "__main__":
solve()
この解説は gemini-3.5-flash-high によって生成されました。
投稿日時:
最終更新: