競プロの精進のために学びがあった問題についてまとめています。 目標は 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))
まとめ
比較的スムーズに実装できた。