gotutiyan’s blog

競技プログラミングをやったりopenframeworksでお絵かきをしたりしています。

ABC 032 C 列

問題
C - 列
素数Nの数列の中で、全ての要素の積がKを超えないような、連続した最長の範囲の要素数を求める。

解法
連続した範囲という言葉を聞いたら尺取り法を使うことを考えよう。

尺取り法は、範囲の右端と左端の変数を用意して、範囲における特定の値が大きければ左端を進めて範囲を狭くして、特定の値を小さくする。小さくなれば、また右端を伸ばして、特定の値を調べることをする。この問題では、「範囲の要素全ての積」が特定の値に当たる。

コーナーケースとして、要素の中に1つでも0が含まれていれば、N個全ての要素の積が0になることから、答えは必ずNになる。これは尺取り法では見つけられないので、例外処理する必要がある。

さて、メインは尺取り法の実装について。
範囲の右端をfor文で回しながら1つずつ伸ばして、伸ばす度に今度はwhile()を用いて、要素達の積がKより小さくなるまで左端を縮める。今回は積を見ているので、範囲を伸ばすときには掛け算、縮める時には割ることになる。このwhileを抜けた時、定まっている範囲は答えの条件を満たす範囲になるので、範囲に含まれる要素数(right-left)とansの大小を比較する。

また、whileにおいては保持している左右の変数について、left>rightとなっては破綻するので(左端が右端より小さいのは当然なため)、その注意もしなければならない。
k=0の場合はsum>kをいかなる場合も満たし続けてしまうのでwhileが終わらず、コーナーケースになりうるが、sum>kの他にleft < rightの条件をつけていることで上手く回避できている。範囲の破綻回避のためだけではないのである。

int main() {
    int n,k;
    cin>>n>>k;
    vector<int> v(n);
    rep(i,0,n){
        cin>>v[i];
        if(v[i]==0){
            cout<<n<<endl;
            return 0;
        }
    }
    ll sum=1;
    int left=-1,ans=0;
    for(int right=0;right<n;right++){
        sum*=v[right];
        while(sum>k&&left<right){
            left++;
            sum/=v[left];
        }
        ans=max(ans,right-left);
    }
    
    cout<<ans<<endl;
    return 0;
}