C - 谷の数え上げ / Counting Valleys Editorial by admin Editorial for printing
Claude 4.5 Opus概要
ハイキングコース上の「谷」(両隣より標高が低い地点)の個数を、複数の区間クエリに対して高速に求める問題です。累積和を用いることで、各クエリに \(O(1)\) で答えることができます。
考察
谷の定義の理解
まず「谷」の定義を確認しましょう。チェックポイント \(i\) (\(2 \leq i \leq N-1\))が谷であるとは: - \(H_{i-1} > H_i\)(左隣より低い) - \(H_i < H_{i+1}\)(右隣より低い)
の両方を満たすことです。両端のチェックポイント(\(i=1\) と \(i=N\))は、片側の隣がないため谷にはなれません。
素朴なアプローチとその問題点
各クエリに対して、区間 \([L_j+1, R_j-1]\) を毎回走査して谷を数えると: - 1つのクエリあたり最大 \(O(N)\) - \(Q\) 個のクエリで合計 \(O(NQ)\)
\(N, Q\) がともに最大 \(2 \times 10^5\) なので、\(O(NQ) = O(4 \times 10^{10})\) となり、制限時間に間に合いません。
解決策:前処理と累積和
区間内の谷の個数を高速に求めるには、累積和(Prefix Sum) を使います。
- 事前に各位置が谷かどうかを判定(\(O(N)\))
- 谷フラグの累積和を計算(\(O(N)\))
- 各クエリに \(O(1)\) で回答
アルゴリズム
Step 1: 谷の判定
配列 is_valley[i] を用意し、位置 \(i+1\)(1-indexed)が谷なら 1、そうでなければ 0 を格納します。
例: H = [5, 3, 7, 2, 8, 4, 9]
位置: 1 2 3 4 5 6 7
位置2: H[1]=5 > H[2]=3, H[2]=3 < H[3]=7 → 谷 ✓
位置3: H[2]=3 < H[3]=7 → 条件を満たさない
位置4: H[3]=7 > H[4]=2, H[4]=2 < H[5]=8 → 谷 ✓
...
Step 2: 累積和の構築
prefix[i] = 位置 1 から位置 \(i\) までの谷の個数
Step 3: クエリ処理
区間 \([L, R]\) の両端を除いた \([L+1, R-1]\) 内の谷の個数は: $\(\text{count} = \text{prefix}[R-1] - \text{prefix}[L]\)$
ただし、\(L+1 > R-1\)(区間内に判定対象がない)場合は 0 を返します。
例: 区間 [1, 5] の場合
両端を除くと [2, 4] が判定対象
prefix[4] - prefix[1] で計算
計算量
- 時間計算量: \(O(N + Q)\)
- 谷の判定: \(O(N)\)
- 累積和の構築: \(O(N)\)
- 各クエリの処理: \(O(1) \times Q = O(Q)\)
- 空間計算量: \(O(N)\)
- 谷フラグ配列と累積和配列
実装のポイント
インデックスの変換に注意: 問題文は 1-indexed ですが、Python の配列は 0-indexed です。変換を丁寧に行いましょう。
境界条件の処理: 区間 \([L, R]\) で \(R - L \leq 2\) の場合、両端を除くと判定対象が存在しない(または 1 点のみ)ことがあります。
累積和の定義:
prefix[i]を「位置 \(i\) 未満の累積」と定義すると、区間 \([a, b]\) の和がprefix[b+1] - prefix[a]で求まり、off-by-one エラーを防ぎやすくなります。入出力の高速化: \(Q\) が大きいため、
sys.stdin.readlineや結果の一括出力('\n'.join())を使って入出力を高速化しています。ソースコード
import sys
def main():
input = sys.stdin.readline
N, Q = map(int, input().split())
H = list(map(int, input().split()))
# 各位置が谷かどうかを判定 (1-indexed で考える)
# is_valley[i] = 1 if position i+1 (1-indexed) is a valley
is_valley = [0] * N
for i in range(1, N - 1): # 0-indexed: 1 to N-2, 1-indexed: 2 to N-1
if H[i - 1] > H[i] and H[i] < H[i + 1]:
is_valley[i] = 1
# 累積和を計算
# prefix[i] = is_valley[0] + ... + is_valley[i-1]
prefix = [0] * (N + 1)
for i in range(N):
prefix[i + 1] = prefix[i] + is_valley[i]
# クエリ処理
results = []
for _ in range(Q):
L, R = map(int, input().split())
# 区間 [L, R] の両端を除く、つまり L+1 から R-1 まで (1-indexed)
# 0-indexed では L から R-2 まで
# 谷の判定対象は 2 <= i <= N-1 (1-indexed) のみ
# 区間内で谷になりうるのは L+1 <= i <= R-1 かつ 2 <= i <= N-1
left = L + 1 # 1-indexed, 区間の左端の次
right = R - 1 # 1-indexed, 区間の右端の前
if left > right:
results.append(0)
else:
# 0-indexed に変換: left-1 から right-1 まで
# prefix sum: prefix[right] - prefix[left-1]
count = prefix[right] - prefix[left - 1]
results.append(count)
print('\n'.join(map(str, results)))
if __name__ == "__main__":
main()
この解説は claude4.5opus によって生成されました。
posted:
last update: