ABC 32 C - 列 ( Crawling / log() / Segment Tree )

C: 列 - AtCoder Beginner Contest 032 | AtCoder
Crawling. O( n ).

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e5 + 5;
const int MAXK = 1e9 + 9;
typedef long long ll;

int n, k;
int s[ MAXN ];

void solve(){
    if( count( s, s + n, 0 ) ){
        printf("%d\n", n);
        return;
    }
    int product = 1;
    int rb = 0;
    int ans = 0;
    for(int lb = 0; lb < n; ++lb){ // [ lb, rb )
        for( ; rb < n && (ll)product * s[ rb ] <= k; ++rb )
            product *= s[ rb ];
        ans = max<int>( ans, rb - lb );
        if( lb < rb ) product /= s[ lb ];
        else ++rb;
    }
    printf("%d\n", ans);
}

int main(){
    scanf("%d%d", &n, &k);
    for(int i = 0; i < n; ++i)
        scanf("%d", &s[ i ]);
    solve();
    return 0;
}

Logをとってあげれば、和の問題になり、二分探査も実現可能となる。O( n lg n )

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e5 + 5;
const int MAXK = 1e9 + 9;
const double EPS = 1e-11;

int n, k;
int s[ MAXN ];

double logs[ MAXN ];
double plogs[ MAXN ];
void solve(){
    if( count( s, s + n, 0 ) ){
        printf("%d\n", n);
        return;
    }
    for(int i = 0; i < n; ++i){
        logs[ i ] = log10( (double)s[ i ] );
        plogs[ i + 1 ] = plogs[ i ] + logs[ i ];
    }
    double logk = log10( k );
    int ans = 0;
    for(int i = 1; i <= n; ++i){
        int lb = i, rb = n, ok = -1;
        while( lb <= rb ){
            int mid = ( lb + rb ) / 2;
            if( plogs[ mid ] - plogs[ i - 1 ] <= logk + EPS )
                ok = mid, lb = mid + 1;
            else
                rb = mid - 1;
        }
        ans = max<int>( ans, ok - i + 1);
    }
    printf("%d\n", ans);
}

int main(){
    scanf("%d%d", &n, &k);
    for(int i = 0; i < n; ++i)
        scanf("%d", &s[ i ]);
    solve();
    return 0;
}

暴力的にセグメント木を使うのも手。

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e5 + 5;
const int MAXK = 1e9 + 9;
typedef long long ll;

int n, k;
int s[ MAXN ];

struct itvt{
    ll val;
    int lb, rb;
    itvt *lc, *rc;
    itvt(): lc(NULL), rc(NULL){}
    void pull(){
        val = lc->val * rc->val;
    }
};

itvt* buildItvt(int lb, int rb){
    itvt *t = new itvt();
    t->lb = lb, t->rb = rb;
    if( lb == rb ){
        t->val = s[ lb ];
        return t;
    }
    int mid = ( lb + rb ) / 2;
    t->lc = buildItvt( lb, mid );
    t->rc = buildItvt( mid + 1, rb );
    t->pull();
    return t;
}

ll qpro(itvt *t, int ql, int qr){
    if( qr < t->lb || t->rb < ql ) return 1LL;
    if( ql <= t->lb && t->rb <= qr ) return t->val;
    return qpro( t->lc, ql, qr ) * qpro( t->rc, ql, qr );
}

void solve(){
    if( count( s, s + n, 0 ) ){
        printf("%d\n", n);
        return;
    }
    itvt *root = buildItvt( 0, n - 1 );
    int rb = 0;
    int ans = 0;
    for(int lb = 0; lb < n; ++lb){
        while( rb < n && qpro( root, lb, rb ) <= k )
            ++rb;
        ans = max<int>( ans, rb - lb );
    }
    printf("%d\n", ans);
}

int main(){
    scanf("%d%d", &n, &k);
    for(int i = 0; i < n; ++i)
        scanf("%d", &s[ i ]);
    solve();
    return 0;
}