Official

C - 谷の数え上げ / Counting Valleys Editorial by physics0523 Editorial for printing


ポイント \(i\) が谷であるかどうかは \(H_{i-1}>H_i\) かつ \(H_i<H_{i+1}\) であるかどうかを調べればわかります。

以下の値をあらかじめ求めておくことを考えます。

\(sum[k]=\{\) ポイント \(1,2,\dots,k\) の中に谷がいくつあるか \(\}\)

本問題の目的は、以下の値を \(Q\) 回求めることです。

  • ポイント \(L+1,L+2,\dots,R-1\) に谷がいくつあるか

普通に計算すると時間計算量 \(O(R-L)\) かかってしまい、これを毎回やっていると実行時間制限に間に合いませんが、予め \(sum\) を計算しておくことで \(sum[R-1]-sum[L]\) として時間計算量 \(O(1)\) で求めることができます。

このようなテクニックは 累積和 と呼ばれます。類題が多数存在するので、解いておくとよいでしょう。

本解法の時間計算量は \(O(N+Q)\) です。

実装例 (C++):

#include<bits/stdc++.h>

using namespace std;

int main(){
  int N,Q;
  cin >> N >> Q;
  vector<int> H(N+1);
  for(int i=1;i<=N;i++){
    cin >> H[i];
  }
  vector<int> sum(N+1,0);
  for(int i=2;i<N;i++){
    sum[i]=sum[i-1];
    if(H[i-1]>H[i] && H[i]<H[i+1]){sum[i]++;}
  }
  while(Q--){
    int L,R;
    cin >> L >> R;
    cout << sum[R-1]-sum[L] << "\n";
  }
  return 0;
}

posted:
last update: