【競プロ典型90問】034 - There are few types of elements（★4）

概要・感想

尺取法ってのもなかなか思いつかなかったし、バグらせるしで大変だった。

[l, r]が各lに対する条件を満たす区間で最も長いものとなる。

提出コード

n, k = map(int, input().split())
a = list(map(int, input().split()))

da = {v: 0 for v in set(a)}

l = 0
r = 0
cnt = 0
rlim = [0] * n
skip = False

while l < n:
    # print(l, r, cnt)
    while (not skip) and r < n - 1 and cnt <= k:
        da[a[r]] += 1
        if da[a[r]] == 1:
            cnt += 1
        if r + 1 == n or (da[a[r+1]] == 0 and cnt == k):
            skip = True
            break
        r += 1

    # print(l,r, da)
    rlim[l] = r
    da[a[l]] -= 1
    if da[a[l]] == 0:
        cnt -= 1
        if r < n - 1:
            skip = False
            r += 1
    l += 1

# print(rlim)
# print(a)
ans = 0
for i in range(n):
    ans = max(ans, rlim[i]-i+1)
print(ans)