C - 谷の数え上げ / Counting Valleys Editorial by admin Editorial for printing
Qwen3-Coder-480B概要
各区間について、内部にある「谷」となるチェックポイントの個数を高速に求めるクエリ処理を行う問題です。
考察
この問題では、各区間 \([L_j, R_j]\) において、両端を除くチェックポイントの中で「谷」になっているものを数える必要があります。
ここでいう「谷」とは、あるチェックポイント \(i\) が \(H_{i-1} > H_i < H_{i+1}\) を満たすことを指します。つまり、両隣の標高よりも真に低いという条件です。
素朴な方法として、各クエリごとに区間内の該当するインデックスを一つずつ見て「谷かどうか」を判定する方法がありますが、これでは最大で \(O(N \cdot Q)\) の計算量となり、制約が \(N, Q \sim 2 \times 10^5\) なので間に合いません(TLE)。
そこで、「事前に各インデックスが谷かどうかを前処理しておき、区間和を高速に求められるようにする」ことを考えます。つまり、
- 各インデックス \(i\) について、それが谷かどうかを \(0/1\) で記録した配列
is_valleyを作成。 - この配列の累積和を取ることで、任意の区間 \([L, R]\) 内の谷の個数を定数時間で求められるようにする。
この累積和を利用することで、各クエリに応答する計算量が \(O(1)\) になり、全体で \(O(N + Q)\) となります。
また、問題文では「両端は谷の判定対象外」とあるので、カウントするのは区間 \([L+1, R-1]\) の範囲内に限ります。もし \(L+1 > R-1\) であれば、その区間には谷が存在しないので答えは \(0\) になります。
例えば、入力が以下のような場合:
H = [5, 2, 4, 1, 6]
このとき、谷となるのはインデックス \(2\)(値=2)と \(4\)(値=1)です(1-indexed)。
したがって、is_valley = [0, 1, 0, 1, 0] となり、累積和をとると区間内の谷の個数が高速に求められます。
アルゴリズム
- 各インデックス \(i\)(\(1 \leq i \leq N-2\))について、\(H_{i-1} > H_i < H_{i+1}\) なら
is_valley[i] = 1とする。 is_valleyの累積和配列acc_valleyを構築する。- 各クエリ \([L_j, R_j]\) に対し、区間 \([L_j+1, R_j-1]\) 内の谷の個数を
acc_valley[R_j-1] - acc_valley[L_j]で求める。
計算量
- 時間計算量: \(O(N + Q)\)
- 空間計算量: \(O(N)\)
実装のポイント
- 累積和は1-indexedで持つことで境界処理が簡単になる。
- クエリの区間が狭すぎて谷が存在しない場合(\(L+1 > R-1\))は答えを \(0\) にする必要がある。
- 入力を高速に読み込むために
sys.stdin.readを使用している。
## ソースコード
```python
import sys
from itertools import accumulate
def main():
import sys
input = sys.stdin.read
data = input().split()
N = int(data[0])
Q = int(data[1])
H = list(map(int, data[2:N+2]))
# 前処理:各位置が谷かどうかを判定し、累積和を計算
is_valley = [0] * N
for i in range(1, N-1):
if H[i-1] > H[i] < H[i+1]:
is_valley[i] = 1
# 累積和配列を作成(1-indexed)
acc_valley = [0] * (N + 1)
for i in range(N):
acc_valley[i+1] = acc_valley[i] + is_valley[i]
# クエリ処理
results = []
idx = N + 2
for _ in range(Q):
L = int(data[idx])
R = int(data[idx+1])
idx += 2
# 区間[L,R]内の谷の数を求める(両端は含まない)
# 谷の判定対象は L+1 から R-1 まで
if L + 1 > R - 1:
results.append(0)
else:
count = acc_valley[R-1] - acc_valley[L]
results.append(count)
print('\n'.join(map(str, results)))
if __name__ == "__main__":
main()
この解説は qwen3-coder-480b によって生成されました。
posted:
last update: