寝癖頭の解法

学習中の覚え書きを投稿、更新していきます。

Aizu Online Judge in C++ #DSL_3_A : The Smallest Window I

Aizu Online Judge(AOJ)の過去問から、その提出コードの解答例です。

・問題 "The Smallest Window I"
https://onlinejudge.u-aizu.ac.jp/problems/DSL_3_A
・最も短い部分列の長さ

僕が作成、提出したコードは、以下のとおりです。

Aizu Online Judge in C++ #DSL_3_A : The Smallest Window I
/*
Aizu Online Judge in C++ #DSL_3_A : The Smallest Window I
https://onlinejudge.u-aizu.ac.jp/problems/DSL_3_A
 提出コードの解答例
 https://neguse-atama.hatenablog.com
*/
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
ll a[100010];
int main(void){
    ll n,S;
    cin>>n>>S;
    for(ll i=0;i<n;i++){
        cin>>a[i];
    }
    ll ans=n+1;
    for(ll s=0,t=0,sum=0;;ans=min(ans,t-s),sum-=a[s++]){
        while(t<n && sum<S){
            sum+=a[t++];
        }
        if(sum<S){
            break;
        }
    }
    if(ans>n){
        cout<<0<<endl;
    }else{
        cout<<ans<<endl;
    }
    return 0;
}

設問の出典は、プログラミング問題のオンライン採点システム「Aizu Online Judge(AOJ)」です。
http://judge.u-aizu.ac.jp/onlinejudge/