典型90 034 – There are few types of elements（★4）

競プロの精進のために学びがあった問題についてまとめています。目標は AtCoder 水色！

今のレートは茶色です。

問題

典型90 034 – There are few types of elements（★4）を解きました。

考察

「その部分列に含まれている要素は K 種類以下の値からなる」ような連続する部分列のうち、最も長いものを求める問題。

似たような問題を区間尺取り法で解いた記憶があるものの、微妙に違いそう。

考え方を変えてみたときに、K種類ではなく、最も長いものの長さMを対象としてみることにする。

答えとなるMは、10^5までのどこかの値となるので、答えの範囲で2分探索をすることで絞りこめる。

一方、K種類以下の値となる長さMの部分列が存在するかどうかは、区間尺取り法でO(N)で求めることができる。

よって、全体の計算量はO(NlogN)となるので、実行時間に間に合う。

コード

from collections import Counter
from bisect import bisect_left, bisect_right

N, K = map(int,input().split())
A = list(map(int,input().split()))
MAX = pow(10, 18) + N + 10

def check(mid):
    CNT = Counter(A[:mid])
    if len(CNT) <= K:
        return True

    for i in range(N - mid):
        CNT[A[i]] -= 1
        CNT[A[mid+i]] += 1
        if CNT[A[i]] == 0:
            del CNT[A[i]]
        if len(CNT) <= K:
            return True

    return False

def search_x(left, right):
    while right - left > 1:
        mid = (right + left) // 2
        if check(mid):
            left = mid
        else:
            right = mid
    return left

print(search_x(1, N+1))