ABC 032 C - 列

問題

問題概要

省略

解法

しゃくとり法をやるだけなんだけど、すぐにうまくできない。

ミス

尺取り法バグらしまくってうまくできない。

コード

尺取り法

#include <iostream>
#include <cstdio>
#include <set>
#include <vector>
#include <algorithm>
using namespace std;
typedef long long ll;
#define rep(i,n) for(int i=0;i<(n);i++)
#define reps(i,f,n) for(int i=(f);i<(n);i++)
const int INF = 1e9;
 
ll s[100010];

int main(void){
    int n, k; cin >> n >> k;
    bool f = false;
    rep(i, n){
        ll t; cin >> t;
        s[i] = t;
        if(t == 0)f = true;
    }
    if(f){//1つでも0が含まれていれば、長さ　n にできる
        printf("%d\n", n);
        return 0;
    }
 
    int ans = 0;
    int l = 0, r = 0;
    ll acc = 1;
    while(r < n){
        while(r < n && acc * s[r] <= k){
            acc *= s[r];
            r++;
        }
        ans = max(ans, r - l);
        if(l != r){
            acc /= s[l];
            l++;
        }else{
            l++; r++;
        }
    }
 
    printf("%d\n", ans);
    return 0;
}

segtree + 尺取り法

#include <iostream>
#include <cstdio>
#include <set>
#include <vector>
#include <algorithm>
using namespace std;
typedef long long ll;
#define rep(i,n) for(int i=0;i<(n);i++)
#define reps(i,f,n) for(int i=(f);i<(n);i++)
const int INF = 1e9;
 
const int MAX_N = 1 << 18;
int size;
ll seg[MAX_N * 2];//segは欲しい情報
struct segtree{
    segtree(int n){
        size = 1;
        while(size < n) size *= 2;//要素数を2のべき乗に
    }
 
    void update(int k, ll v){//k番目の値をvに変更
        k += size - 1;
        seg[k] = v;
        //上りながら更新
        while(k > 0){
            k = (k - 1) / 2;
            seg[k] = seg[k * 2 + 1] * seg[k * 2 + 2];
        }
    }
 
    //[a, b)の積を求める
    ll query(int a, int b, int k = 0, int l = 0, int r = size){
        if(r <= a || b <= l) return 1;//積に影響を与えない 1
        if(a <= l && r <= b) return seg[k];
        ll x = query(a, b, k * 2 + 1, l, (l + r) / 2);//左の子の積
        ll y = query(a, b, k * 2 + 2, (l + r) / 2, r);//右の子の積
        return x * y;
    }
};
 
 
int main(void){
    int n, k; cin >> n >> k;
    segtree st(n);
    bool f = false;
    rep(i, n){
        ll t; cin >> t;
        if(t == 0)f = true;
        st.update(i, t);
    }
    if(f){//1つでも0が含まれていれば、長さ　n にできる
        printf("%d\n", n);
        return 0;
    }
 
    int ans = 0;
    //[l, r)の長さが最大となるところを求める。
    int r = 1;
    rep(l, n){//左を1つ縮める
        while(!(l < r))r++;//lがrを超えないように
        while(r <= n && st.query(l, r) <= k) r++;//左を固定して、右を伸ばせるだけのばす
        ans = max(ans, r - l - 1);//[l, r - 1]が条件を満たしている
    }
 
    printf("%d\n", ans);
    return 0;
}

この実装がわかりやすいかも

#include <iostream>
#include <cstdio>
#include <set>
#include <vector>
#include <algorithm>
using namespace std;
typedef long long ll;
#define rep(i,n) for(int i=0;i<(n);i++)
#define reps(i,f,n) for(int i=(f);i<(n);i++)
const int INF = 1e9;
 
ll s[100010];

int main(void){
    int n, k; cin >> n >> k;
    bool f = false;
    rep(i, n){
        ll t; cin >> t;
        s[i] = t;
        if(t == 0)f = true;
    }
    if(f){//1つでも0が含まれていれば、長さ　n にできる
        printf("%d\n", n);
        return 0;
    }
    if(k == 0){
        printf("0\n");
        return 0;
    }
 
    int ans = 0;
    int l = 0, r = 0;
    ll acc = 1;

    //[l, r]
    while(1){
        if(acc <= k){//右を進める　ans 答えを更新
            ans = max(ans, r - l);
            if(r == n) break;
            acc *= s[r++];
        }else{
            acc /= s[l++];
        }
    }
 
    printf("%d\n", ans);
    return 0;
}