解説 - AtCoder Weekday Contest 0145 Beta

コンテスト時間: 2026-08-28 20:00:00+0900 ~ 2026-08-28 21:00:00+0900 (60分) AtCoderホームへ戻る

公式

E - 山型整地 / Mountain-Shaped Leveling 解説 by admin

gemini-3.5-flash-high

Overview

This problem asks for the minimum number of operations to transform a given sequence of land heights $H$ into a mountain-shaped sequence $H'$ by repeatedly performing the operation “decrease the height of an interval by $1$”.

Although the operation seems complex at first glance, by focusing on the “differences” between adjacent elements and their “prefix sums”, we can iterate through all possible peak positions $k$ and calculate the minimum cost for each $k$ in $O(1)$ time. This allows us to solve the problem in $O(N)$ overall time complexity.

Analysis

1. Reformulating the Operation and Focusing on “Adjacent Differences”

Let us consider the operation “decrease the height of the interval $[l, r]$ by $1$” from the perspective of the differences between adjacent elements $D_i = H_i - H_{i-1}$ (where we define $H_0 = H_{N+1} = 0$). When we perform this operation, the differences change as follows: - $D_l$ decreases by $1$ - $D_{r+1}$ increases by $1$ - Other $D_i$ remain unchanged

From this property, it is a well-known fact that the minimum number of operations required to reduce all elements of the sequence $H$ to $0$ is equal to the sum of the positive adjacent differences $\sum \max(0, D_i)$. (Similarly, this is also equal to the sum of the absolute values of the negative adjacent differences. Since both the initial and final states are $0$, the total increase and the total decrease must be equal).

2. Conditions for a Mountain-Shaped Sequence

Our goal is to make the modified sequence $H'$ mountain-shaped, with the $k$-th element as the peak. A sequence is mountain-shaped if it satisfies the following conditions: - Left side ($1 \le i \le k$): Monotonically non-decreasing. That is, all adjacent differences are at least $0$ (no decreases: $D'_i \ge 0$). - Right side ($k+1 \le i \le N+1$): Monotonically non-increasing. That is, all adjacent differences are at most $0$ (no increases: $D'_i \le 0$).

Since we can only “decrease” heights from the original sequence $H$, to achieve a mountain shape, we must shave off the parts that violate these conditions.

Cost for the left side ($1 \le i \le k$): To make the left side monotonically non-decreasing, we must eliminate all “decreasing parts ($D_i < 0$)” in the original $H$ on the left side. The minimum amount of reduction required to eliminate these is the sum of the absolute values of the decreases on the left side. $$SM[k] = \sum_{i=1}^k \max(0, -D_i)$$
Cost for the right side ($k+1 \le i \le N+1$): To make the right side monotonically non-increasing, we must eliminate all “increasing parts ($D_i > 0$)” in the original $H$ on the right side. The minimum amount of reduction required to eliminate these is the sum of the increases on the right side. $$SP[N+1] - SP[k] \quad \left(\text{where } SP[x] = \sum_{i=1}^x \max(0, D_i)\right)$$

3. Calculating the Minimum Cost

Since the operations on the left and right sides can be performed independently, the minimum number of operations $\text{Cost}(k)$ to make the sequence mountain-shaped with the peak at index $k$ is simply the sum of the costs of both sides. $$\text{Cost}(k) = SM[k] + (SP[N+1] - SP[k])$$

Here, - $SP[i]$: Prefix sum of the positive parts of the adjacent differences from $1$ to $i$. - $SM[i]$: Prefix sum of the absolute values of the negative parts of the adjacent differences from $1$ to $i$. - $SP[N+1]$: The sum of the positive parts of the adjacent differences over the entire sequence (which is the total cost to reduce everything to $0$).

We calculate this $\text{Cost}(k)$ for all possible peaks $k$ ($0 \le k \le N$), and the minimum value among them is our answer. By precomputing the prefix sums, the cost for each $k$ can be obtained in $O(1)$ time.

Algorithm

Adding Sentinels: Add $0$ to the beginning and end of the array $H$, setting $H_0 = 0$ and $H_{N+1} = 0$. This allows us to handle the boundaries uniformly.
Constructing Prefix Sums: Compute the adjacent differences $D_i = H_i - H_{i-1}$ sequentially, and construct the following two prefix sum arrays:
- $SP[i]$: Prefix sum of $D_i$ when $D_i > 0$
- $SM[i]$: Prefix sum of $|D_i|$ when $D_i < 0$
Searching for the Minimum Value: For each position $k$ from $0$ to $N$, calculate $\text{Cost}(k) = SM[k] + SP[N+1] - SP[k]$ and find the minimum value.

Complexity

Time Complexity: $O(N)$ Constructing the prefix sums takes $O(N)$ time, and searching for the minimum value over all $k$ takes $O(N)$ time. Thus, the overall time complexity is $O(N)$, which runs fast enough even for the constraint $N = 10^6$ in the problem.
Space Complexity: $O(N)$ We use $O(N)$ memory to store the prefix sum arrays $SP$ and $SM$.

Implementation Points

Fast I/O: In Python, when the number of inputs is on the scale of $10^6$, using input() might cause a Time Limit Exceeded (TLE). Therefore, we read all inputs at once using sys.stdin.read().split().
On the Calculation of Uk in the Code: The following part of the provided code:
```
val1 = SM[k]
val2 = SP[k] - H[k]
Uk = val1 if val1 > val2 else val2
```
Mathematically, since $H_k = SP[k] - SM[k]$ holds, we have $SP[k] - H[k] = SM[k]$, meaning val1 and val2 are always equal. Therefore, Uk is always equal to SM[k], and the cost formula can be simplified as SM[k] + sp_total - SP[k].

Source Code

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()

This editorial was generated by gemini-3.5-flash-high.

投稿日時:
最終更新: