公式
C - 谷の数え上げ / Counting Valleys 解説
by
C - 谷の数え上げ / Counting Valleys 解説
by
physics0523
印刷ページ
ポイント \(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;
}
投稿日時:
最終更新:
