AtCoder の問題を解くために必要な実力を付けるために作られた「典型問題」を解いていく企画として、「典型90」があります。
今回は、その内、の34問目である「034 – There are few types of elements（★4）」を解説していきたいと思います。
なにか、間違っているところなどありましたら、@EitaSugiまで、ご指導ご鞭撻の程、よろしくお願い致します！
問題名 【034 – There are few types of elements（★4）】
入力
N: 数列の長さ
K: 部分列の長さ
a[i]: 長さNの数列のi番目の要素
考察
今回は、任意のLとRを決めた際に、[L,R)に含まれる数字の種類を最大にする問題です。
愚直にL,Rについて[0,N)を探索してしまうと、TLEになってしまいます。
※N≤100,000のため、O(N^2)はTLEする
ここで、注目したいのは、RはLよりも右側になければならないということです
(L,Rなので当たり前のようですが重要です)
つまり、左端から探索を始めた場合、
- [L,R)区間において、K種類以下ならRを右にやり範囲を広げ
- K種類以上なら、Lを右にやり範囲狭める
ことですべての範囲について探索できます。
このように任意の区間をO(2N)で解く方法を尺取法といいます(違ったらすみません)
そのため、今回は尺取法を用いて、L,Rについて探索を行えば解けます。
典型解法：尺取法
コード
import collections
N,K = map(int, input().split())
A = list(map(int, input().split()))
cnt = collections.defaultdict(int)
for i in range(K):
cnt[A[i]] += 1#[0,K)の中に何種類の数字があるかカウント
r = K
l = 0
ans = 0
for r in range(K,N):#rの取りうる範囲である[K,N)まで探索
cnt[A[r]]+=1#A[r]のカウント+1
while len(cnt) > K and l < N-K:#もしK種類よりも多い数字がカウントされたら範囲を狭める必要がある
# print(len(cnt),l,r)
cnt[A[l]] -=1#A[l]のカウント-1し
if cnt[A[l]] == 0:#もし、A[l]のカウントが0になったら
del cnt[A[l]]#cntからA[l]を消去し、cntの長さを短くする
l += 1#lを一つ右に動かす
ans = max(ans,r-l+1)#連続する部分列の最大値を記憶
print(ans)
コメント