ABC032C - 列

atcoder.jp

問題

長さNの数列の連続する部分列の要素の積がKを超えない最長の部分列の長さを求める問題です。

考察

サンプルで数列の要素に０が含まれる場合があり，この場合はすべての積が０になるのでNを出力します。

そのほかの場合には，順番に最初からかけていってKを超えたところまでの長さの最長値を更新し，Kを超えた場合，次のスタートを一つ先の要素から始めるようにしました。

単純なfor文では書けなかったため，while文で回して最後まで行ったらbreakする形にしました。

計算時間が間に合うか微妙かなとも思いましたが，ぎりぎり間に合いました。
想定解とは違うかも知れませんので後で解説を確認します。

最初の提出は，数ケースでWAしました。
最後までKを超えなかった場合のエラーだと気づき，Kを超えなかった場合のフラグでNを出力するように改良してACできました。

ACしたコード

だいぶごちゃごちゃしてしまいました。

#include <bits/stdc++.h>
using namespace std;

int main() {
  int N;
  long long K;
  cin>>N>>K;
  long long a[100010];
  int flag=0;
  int flag2=1;
  for(int i=0;i<N;i++){
    cin>>a[i];
    if(a[i]==0){
      flag=1;
    }
  }
  if(flag){
    //cout<<"#"<<N<<"$"<<K<<endl;
    cout<<N<<endl;
    return 0;
  }
  int temp1=0;
  int ans=0;
  int maxans=0;
  long long temp=1;
  while(1){
    flag=0;
    for(int i=temp1;i<N;i++){
      temp*=a[i];
      //cout<<i<<" "<<temp<<endl;
      if(temp>K){
        ans=i-temp1;
        maxans=max(maxans,ans);
        temp1++;
        ans=0;
        flag=1;
        flag2=0;
        temp=1;
        break;
      }
    }
    if(flag){
      continue;
    }
    else{
      break;
    }
  }
  if(flag2){
    cout<<N<<endl;
    return 0;
  }
  cout<<maxans<<endl;
  return 0;
}