Official

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) を使います。

  1. 事前に各位置が谷かどうかを判定(\(O(N)\))
  2. 谷フラグの累積和を計算(\(O(N)\))
  3. 各クエリに \(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. インデックスの変換に注意: 問題文は 1-indexed ですが、Python の配列は 0-indexed です。変換を丁寧に行いましょう。

  2. 境界条件の処理: 区間 \([L, R]\) で \(R - L \leq 2\) の場合、両端を除くと判定対象が存在しない(または 1 点のみ)ことがあります。

  3. 累積和の定義: prefix[i] を「位置 \(i\) 未満の累積」と定義すると、区間 \([a, b]\) の和が prefix[b+1] - prefix[a] で求まり、off-by-one エラーを防ぎやすくなります。

  4. 入出力の高速化: \(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: