https://kyopro.hateblo.jp/entry/2019/02/07/002409

問題. 列

長さ $n$ の非負整数列 $s = (s_1, \ldots, s_n)$ と整数 $k$ が与えられる． $s$ の連続部分列でその積が $k$ 以下となるものの長さの最大値を答えよ．

制約： $1 \le n \le 10^5$ ，　 $0 \le s_i \le 10^9$

解法．尺取り法

$s$ の要素で 0 となるものが存在するとき答えは $n$ となるので，それ以外の場合について考える．
各添字 $i \in \{1, \ldots, n\}$ に対して，左端が $i$ の連続部分列でその積が $k$ 以下となる長さが最大のものの区間を左閉右開区間で $[i, r_i)$ と表す．このとき，任意の $i < j$ に対して $r_i \le r_j$ となるので，先頭から順番に $r_i$ の値を全探索する．ただし， $i$ 番目まで探索したあとに $i + 1$ 番目の $r_{i+1}$ は $r_i$ から探索する．各要素は高々定数回しか参照されないので全体で $O(n)$ 時間で答えを求めることができる．

計算時間： $O(n)$

ソースコードを表示

#include <bits/stdc++.h>

using namespace std;

using ll = long long;

int Solve() {
    ll n, k;
    cin >> n >> k;

    vector<ll> s(n);
    for (int i = 0; i < n; ++i) {
        cin >> s[i];
        if (s[i] == 0) return n;
    }

    int l = 0, r = 0, res = 0;
    ll prod = 1;
    while (l < n) {
        while (r < n && prod * s[r] <= k) prod *= s[r++];
        res = max(res, r - l);
        if (l == r) prod *= s[r++];
        prod /= s[l++];
    }
    return res;
}

int main() {
    cin.tie(0); ios::sync_with_stdio(false);

    cout << Solve() << endl;

    return 0;
}

尺取り法を実装するときいつも戸惑う．
左閉右開区間にすると少しキレイに書ける．