ABC032 C問題：列

問題. 列

長さ の非負整数列 と整数 が与えられる． の連続部分列でその積が 以下となるものの長さの最大値を答えよ．

制約： ，　

解法．尺取り法

の要素で 0 となるものが存在するとき答えは となるので，それ以外の場合について考える．
各添字 に対して，左端が の連続部分列でその積が 以下となる長さが最大のものの区間を左閉右開区間で と表す．このとき，任意の に対して となるので，先頭から順番に の値を全探索する．ただし， 番目まで探索したあとに 番目の は から探索する．各要素は高々定数回しか参照されないので全体で 時間で答えを求めることができる．

計算時間：

ソースコードを表示

#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;
}

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