AtCoder Beginner Contest 032 C - 列

問題

abc032.contest.atcoder.jp

解法

まず, s[i] のいずれかが 0 だったらすべての値を掛け算した結果は 0 になるので, 答えは N です。
そうでない場合に K = 0 だったら, s[i] > K が任意の i で成り立つので, 答えは 0 です。
それ以外の場合は, しゃくとりっぽく出来ます。左端の数 l を決めると, 右端 r がどこまで伸びるかが決まります。その後左端を一つ右からスタートすることにすると, ([l, r] の区間の掛け算 >= [l+1, r] の区間の掛け算) なので, l+1 番目からスタートするときは, 右端の数は r から始めても問題ありません。

このようにすると, 計算量は左端で調べる数の O(N) と, 右端で調べる数の O(N) で, 合計 O(2N) です。

const int MAXN = 100010;
int s[MAXN];

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    int N, K;
    cin >> N >> K;
    for (int i = 0; i < N; i++) cin >> s[i];
    {
        bool e0 = false;
        for (int i = 0; i < N; i++) e0 |= (s[i] == 0);
        if (e0) {
            cout << N << endl;
            return 0;
        }
        if (K == 0) {
            cout << 0 << endl;
            return 0;
        }
    }
    ll mult = 1;
    int t = 0, ans = 0;
    for (int i = 0; i < N; i++) {
        while (t < N && mult <= K) mult *= s[t++];
        ans = max(ans, t-i-1+(mult <= K));
        mult /= s[i];
    }
    cout << ans << endl;
    return 0;
}