B. Nastya and Door (Codeforces Round #637 Div. 2)

Nastya was very confused じゃあないんだよ。困惑してるのはこっちだよ。

問題

https://codeforces.com/contest/1341/problem/B

問題概要

峠を境に地区が分かれている地域がある。

その地域の幅nの区間ごとの標高と、幅kが与えられるので、幅kの中に含むことのできる最大の地区数と、その時のkの左端を答えよ。ただし候補が複数あるときは最も左側のものを採用すること。

考察

要するに、幅kの中に峠がいくつあるかを調べて、それが一番大きいものが答えとなります。

各地点が峠であるかどうかは、a[i-1] < a[i] and a[i] > a[i + 1]で判別可能です。

あとは左端から幅kの区間に峠がいくつ含まれるかを全探索していけばよいですが、都度峠であるかどうかを見ると計算量がO(nk)になって間に合いません。なので、峠の数を累積和で前処理しておいてO(1)で取り出せるようにしておけばよいです。

#include <bits/stdc++.h>
using namespace std;
 
int main() {
    int t;
    cin >> t;
    while (t--) {
        int n, k;
        cin >> n >> k;
        vector<int> a(n);
        for (int i = 0; i < n; i++) cin >> a[i];
        vector<int> p(n);
        for (int i = 1; i < n - 1; i++) {
            // 峠なら1になる
            if (a[i] > a[i - 1] and a[i] > a[i + 1]) p[i] = 1;
        }
        vector<int> sum(n + 1);
        for (int i = 1; i < n; i++) {
            sum[i + 1] = sum[i] + p[i];
        }
        int ans = 0;
        int ansl = 0;
        for (int i = 0; i < n - k + 1; i++) {
            // 数える時、両端を含まないことに注意
            if (ans < sum[i + k - 1] - sum[i + 1]) {
                ans = sum[i + k - 1] - sum[i + 1];
                ansl = i;
            }
        }
        // 分割後の数は峠の数 + 1、座標は0-indexed -> 1-indexedなので、それぞれ1を足している
        cout << ans + 1 << " " << ansl + 1 << endl;
    }
}