ゆらのふなびと

競プロ, Python, C++

AtCoder Begineer Contest 032 C - 列

問題

C: 列 - AtCoder Beginner Contest 032 | AtCoder

長さ N の非負整数列 S=s1,s2,…,sN と整数 K があります。 あなたの仕事は、以下の条件を満たす S の 連続する 部分列のうち、最も長いものの長さを求めることです。部分列の長さは 1 以上の列でないといけません。

  • その部分列に含まれる全ての要素の値の積は、K 以下である。

もし条件を満たす部分列が一つも存在しないときは、0 を出力してください。

制約

 1 \leq N \leq 10^5

 0 \leq K \leq 10^9

 0 \leq s_i \leq 10^9

解答

部分列を全探索しようとすると O(N^2)になるが、制約上これでは間に合わない。そこで、 O(N)で処理が可能なしゃくとり法を用いる。

このしゃくとり法をどう実装するかというのが問題。通常のi→jの順番で動かすとわかりにくいのでj→iの順番で動かす。つまり、

【以下を繰り返す】

  • 右側をひとつ伸ばす(積にかける)
  • 積がKを超えていたら左端を縮める(積K以下となるまで)

ただし、sに0が含まれる場合は、Kの値にかかわらずs全体の積が0となるので答えはN。

N, K = map(int, input().split())
s = [int(input()) for i in range(N)]
 
if 0 in s:
    print(N)
else:
    i = 0
    ma = 0
    pro = 1
    for j in range(N):
        pro *= s[j]
        while i <= j and pro > K:
            pro //= s[i]
            i += 1
        if i <= j:
            ma = max(ma, j - i + 1)
    print(ma)


しゃくとり法だけで解ける問題は割と基本的な問題だと思うので、しっかり解けるようにしておきたい。