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

問題

https://atcoder.jp/contests/typical90/tasks/typical90_ah

挑戦結果

• 挑戦日：2021/10/08
• 結果：解けた
• 時間：30分ぐらい

考えたこと

• しゃくとり法のように構成すれば良さそう
• 現在見ている左部分(l)と右部分(r)の座標を保持する。
• 登場した数字の個数はdictでカウントする
  • 最初setで数字が登場したかだけで判定しておりWAだった。
• 進め方
  • K個以下の場合：rを右にすすめる。(もっと増える可能性あり)
  • K個以上の場合：lをすすめる。

公式解説

• https://twitter.com/e869120/status/1390798852299448322

解説を読んだふりかえり

• 想定通りだったので、特に話。
• 「最初に座標圧縮を行う場合」というのはなんのことかわからなかった。。。

ソース

N,K = [int(x) for x in input().split()]
A = [int(x) for x in input().split()]

l = -1
r = -1

s = dict()
mm = 0
while l<N:
    if len(s)<=K and r<N:
        mm = max(mm, r-l)
        r+=1
        if r<N:
            s[A[r]] = s.get(A[r],0) + 1
    else:
        l+=1
        if l<N:
            s[A[l]] = s.get(A[l],0) - 1
            if s[A[l]] == 0:
                s.pop(A[l])

print(mm)