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)という手法が非常に有効です。
- 長さ \(N\) の配列 \(A\) を用意し、地点 \(i\) が谷なら \(A[i] = 1\)、そうでなければ \(A[i] = 0\) とします。
- \(A\) の累積和配列 \(S\) を作成します。\(S[k]\) は \(1\) 番目から \(k\) 番目までの地点にある谷の総数とします。
- 区間 \((L, R)\)、つまり \(L+1\) 番目から \(R-1\) 番目までの谷の個数は、 \(S[R-1] - S[L]\) という計算だけで、たった \(O(1)\) で求められます。
アルゴリズム
- 谷のフラグ立て:
\(i = 2\) から \(N-1\) までの各地点について、谷の条件を満たすか判定し、結果を配列(例:
is_valley_count)に記録します。 - 累積和の計算:
上記配列を元に累積和配列
prefix_sumを作成します。prefix_sum[i] = prefix_sum[i-1] + (地点 i が谷なら 1、そうでなければ 0) - クエリへの回答:
各クエリ \([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: