ABC032 C - 列

備忘録

問題

atcoder.jp

回答

import sys
import os
import math
import bisect
import collections
import itertools
import heapq
import re
import queue
from decimal import Decimal

# import fractions

sys.setrecursionlimit(10000000)

ii = lambda: int(sys.stdin.buffer.readline().rstrip())
il = lambda: list(map(int, sys.stdin.buffer.readline().split()))
fl = lambda: list(map(float, sys.stdin.buffer.readline().split()))
iln = lambda n: [int(sys.stdin.buffer.readline().rstrip()) for _ in range(n)]

iss = lambda: sys.stdin.buffer.readline().decode().rstrip()
sl = lambda: list(map(str, sys.stdin.buffer.readline().decode().split()))
isn = lambda n: [sys.stdin.buffer.readline().decode().rstrip() for _ in range(n)]

lcm = lambda x, y: (x * y) // math.gcd(x, y)
# lcm = lambda x, y: (x * y) // fractions.gcd(x, y)

MOD = 10 ** 9 + 7
MAX = float('inf')


def main():
    if os.getenv("LOCAL"):
        sys.stdin = open("input.txt", "r")

    N, K = il()
    S = []
    for n in range(N):
        s = ii()
        if s == 0:
            print(N)
            exit()
        S.append(s)

    ret, r, ml = 0, 0, 1
    for l in range(N):
        while r < N and ml * S[r] <= K:
            ml *= S[r]
            r += 1

        ret = max(ret, r-l)
        if l == r:
            r += 1
        else:
            ml /= S[l]
    print(ret)


if __name__ == '__main__':
    main()

考え方

尺取り法を用いて、連続する部分列から
積がK以下となる最長を求める。

数列Sの積を取る範囲の最も左をl、最も右をrとして、
左端、右端を0, 0から積の計算を始める。
左端(l)が0のとき、右端(r)を進めても積がKを上回らない位置まで右端を進める。

左端(l)がインクリメントされるとき、
積から進めた分だけ減らし(ml /= S[l])、
左端(l)と右端(r)が同位置に達した場合、
右端(r)をインクリメントする。（r += 1)

上記の処理を行い、左端(l)の位置が0 ~ N-1の全ての場合において、
最長の右端(r)の位置を探索する。

注意点として、数列Sの中に0が含まれている場合、
積は必ず0となるため、最長はNとなる。