Official

C - 谷の数え上げ / Counting Valleys Editorial by admin Editorial for printing

gemini-3-flash-thinking

概要

与えられた \(N\) 個の地点の標高データに対し、「両隣よりも標高が低い地点(谷)」の個数を、複数のクエリ(区間 \([L, R]\))に対して効率的に答える問題です。

考察

1. 谷の判定条件

ある地点 \(i\) が「谷」であるかどうかは、その地点の標高 \(H_i\) と両隣の標高 \(H_{i-1}, H_{i+1}\) のみの関係で決まります。 - 条件:\(H_{i-1} > H_i\) かつ \(H_i < H_{i+1}\)

この判定は、各地点について独立に行うことができます。

2. 素朴なアプローチとその限界

各クエリ \([L, R]\) に対して、毎回 \(L+1\) から \(R-1\) までの地点を一つずつ「谷かどうか」判定して数え上げると、最悪の場合 1 つのクエリにつき \(O(N)\) の時間がかかります。 クエリの数は \(Q\) 個あるため、全体の計算量は \(O(N \times Q)\) となります。 本問題では \(N, Q \leq 2 \times 10^5\) であるため、最大で \(4 \times 10^{10}\) 回程度の計算が必要になり、実行時間制限(通常 2 秒程度)に間に合いません。

3. 累積和による高速化

標高データは途中で更新されないため、あらかじめ「どの地点が谷か」を計算しておくことができます。 特定の区間内の「個数」を高速に求めるには、累積和(prefix sum)という手法が非常に有効です。

  1. 長さ \(N\) の配列 \(A\) を用意し、地点 \(i\) が谷なら \(A[i] = 1\)、そうでなければ \(A[i] = 0\) とします。
  2. \(A\) の累積和配列 \(S\) を作成します。\(S[k]\) は \(1\) 番目から \(k\) 番目までの地点にある谷の総数とします。
  3. 区間 \((L, R)\)、つまり \(L+1\) 番目から \(R-1\) 番目までの谷の個数は、 \(S[R-1] - S[L]\) という計算だけで、たった \(O(1)\) で求められます。

アルゴリズム

  1. 谷のフラグ立て: \(i = 2\) から \(N-1\) までの各地点について、谷の条件を満たすか判定し、結果を配列(例:is_valley_count)に記録します。
  2. 累積和の計算: 上記配列を元に累積和配列 prefix_sum を作成します。 prefix_sum[i] = prefix_sum[i-1] + (地点 i が谷なら 1、そうでなければ 0)
  3. クエリへの回答: 各クエリ \([L, R]\) に対し、答えは prefix_sum[R-1] - prefix_sum[L] となります。 ※ \(R-1 < L+1\) となるような短い区間の場合は、この計算結果は \(0\) または負になりますが、累積和の定義通りに計算すれば正しく \(0\) と判定されます。

計算量

  • 時間計算量: \(O(N + Q)\)
    • 谷の判定と累積和の構築に \(O(N)\)、各クエリの回答に \(O(1)\) かかるため、全体で \(O(N + Q)\) となります。
  • 空間計算量: \(O(N)\)
    • 標高データと累積和配列を保持するために \(O(N)\) のメモリを使用します。

実装のポイント

  • 高速な入出力: Pythonの場合、input() を繰り返すと時間がかかるため、sys.stdin.read().split() などで一括で入力を読み込むのが効率的です。

  • インデックスの管理: 問題文は 1-indexed(1始まり)ですが、プログラムの配列は 0-indexed(0始まり)であることが多いため、インデックスのズレに注意が必要です。

  • 境界条件: クエリの範囲が \(L < i < R\) であるため、累積和で引く範囲を間違えないようにしましょう(\(L\) 番目までの累積和を引き、\(R-1\) 番目までの累積和を使います)。

    ソースコード

import sys

def solve():
    # Use fast I/O: read all input at once from standard input
    data = sys.stdin.read().split()
    if not data:
        return
    
    # Convert all input strings to integers at once for efficiency
    # This is faster in Python than converting them one by one in a loop
    nums = list(map(int, data))
    
    N = nums[0]
    Q = nums[1]
    
    # H[0]...H[N-1] correspond to checkpoint elevations H_1...H_N
    H = nums[2:2+N]
    
    # prefix_sum[i] will store the cumulative count of valleys from checkpoint 1 to i.
    # Checkpoints are 1-indexed (1 to N).
    # A checkpoint i (2 <= i <= N-1) is a valley if H[i-2] > H[i-1] < H[i].
    # We initialize an array of size N+1 to handle 1-based indexing easily.
    is_valley_count = [0] * (N + 1)
    for j in range(1, N - 1):
        # j is the 0-based index in H, so H[j] corresponds to checkpoint i = j+1.
        # Checkpoint i is a valley if the elevation at i-1 > elevation at i < elevation at i+1.
        if H[j-1] > H[j] < H[j+1]:
            is_valley_count[j+1] = 1
    
    # Compute the prefix sums from the is_valley_count array.
    # prefix_sum[i] = number of valleys in checkpoints {1, 2, ..., i}.
    prefix_sum = [0] * (N + 1)
    for i in range(1, N + 1):
        prefix_sum[i] = prefix_sum[i-1] + is_valley_count[i]
        
    # Process each of the Q queries.
    results = []
    # Query parameters L_j and R_j start from nums[2+N] onwards.
    query_start_idx = 2 + N
    for k in range(Q):
        L = nums[query_start_idx + 2 * k]
        R = nums[query_start_idx + 2 * k + 1]
        
        # The query asks for the number of valleys at checkpoints i such that L < i < R.
        # This range of checkpoints is {L+1, L+2, ..., R-1}.
        # The count of valleys in this range is prefix_sum[R-1] - prefix_sum[L].
        # Note: If R - 1 < L + 1 (i.e., R - L < 2), the range is empty.
        # Since L < R, R-1 >= L. If R-1 == L, the result is correctly 0.
        ans = prefix_sum[R-1] - prefix_sum[L]
        results.append(str(ans))
        
    # Output all results at once, separated by newlines, for performance.
    sys.stdout.write("\n".join(results) + "\n")

if __name__ == '__main__':
    solve()

この解説は gemini-3-flash-thinking によって生成されました。

posted:
last update: