Official
C - 谷の数え上げ / Counting Valleys Editorial by admin Editorial for printing
DeepSeek V3概要
この問題は、チェックポイントの標高列が与えられたとき、各クエリで指定された区間内(両端を除く)に存在する「谷」の数を効率的に数える問題です。
考察
谷の条件は、\(H_{i-1} > H_i < H_{i+1}\) を満たすことです。各クエリに対して毎回区間内の各点を調べると、最悪の場合 \(O(NQ)\) の計算量となり、制約条件 \(N, Q \leq 2 \times 10^5\) では時間内に処理できません。そこで、前処理を行い、クエリごとに高速に回答できる方法を考える必要があります。
重要な観察は、谷の位置を事前に記録しておき、累積和を使って任意の区間内の谷の数を \(O(1)\) で計算できるようにすることです。これにより、全体の計算量を \(O(N + Q)\) に抑えることができます。
アルゴリズム
前処理:
- 各位置 \(i\) (\(2 \leq i \leq N-1\)) について、谷かどうかを判定します。谷なら \(1\)、そうでなければ \(0\) を記録する配列
is_valleyを作成します。 is_valley配列の累積和配列prefixを構築します。prefix[i]は位置 \(1\) から \(i\) までの谷の総数を表します。
- 各位置 \(i\) (\(2 \leq i \leq N-1\)) について、谷かどうかを判定します。谷なら \(1\)、そうでなければ \(0\) を記録する配列
クエリ処理:
- 各クエリ \([L, R]\) に対して、区間内の谷の数は
prefix[R-1] - prefix[L]で求められます。 - ただし、区間の長さが \(2\) 以下の場合は谷が存在しないため、\(0\) を返します。
- 各クエリ \([L, R]\) に対して、区間内の谷の数は
計算量
- 時間計算量: \(O(N + Q)\)
- 前処理に \(O(N)\)、各クエリの処理に \(O(1)\) です。
- 空間計算量: \(O(N)\)
- 配列
H,is_valley,prefixを保持するため。
- 配列
実装のポイント
配列のインデックスに注意: 入力の \(H\) は0-indexedですが、問題のチェックポイント番号は1-indexedです。実装では
is_valleyのインデックスを1-indexedに合わせています。累積和の計算では、区間 \([L, R]\) 内の和を求める際に
prefix[R-1] - prefix[L]とします。これは、区間の両端 \(L\) と \(R\) を谷の判定対象から除外するためです。ソースコード
import sys
def main():
data = sys.stdin.read().split()
it = iter(data)
n = int(next(it))
q = int(next(it))
H = [int(next(it)) for _ in range(n)]
is_valley = [0] * (n + 2)
for i in range(1, n - 1):
if H[i - 1] > H[i] < H[i + 1]:
is_valley[i + 1] = 1
prefix = [0] * (n + 2)
for i in range(1, n + 1):
prefix[i] = prefix[i - 1] + is_valley[i]
out_lines = []
for _ in range(q):
L = int(next(it))
R = int(next(it))
if R - L < 2:
out_lines.append("0")
else:
res = prefix[R - 1] - prefix[L]
out_lines.append(str(res))
print("\n".join(out_lines))
if __name__ == "__main__":
main()
この解説は deepseekv3 によって生成されました。
posted:
last update: