Atcoder ABC210 Python C問題振り返り

前書き

今回もC問題でACできなかったので振り返ります。
difficulty的には茶色より少し低いくらいなので、このくらいのレベルを安定して解けるようになりたいもんです（笑）。

自分の提出（TLE）

import collections
N,K = map(int,input().split())
C = list(map(int,input().split()))

ans = []

for i in range(N-K+1):
  l = C[i:i+K]
  a = collections.Counter(l)
  c = len(a)
  ans.append(c)

print(max(ans))

修正後の提出（AC確認済み）

import collections
N,K = map(int, input().split())
C = list(map(int, input().split()))

d = {}

cnt = []

for i in range(K):
  d.setdefault(C[i],0)
  d[C[i]] += 1

ans = len(d)

for i in range(K, N):
  d.setdefault(C[i], 0)
  # 右側の差分
  d[C[i]] += 1
  # 左側の差分
  d[C[i-K]] -= 1
  # もし要素数が0になったら、辞書型から削除
  if d[C[i-K]] == 0:
      del d[C[i-K]]
  ans = max(ans, len(d))

print(ans)

感想

なんとなくの方針は立てられるようになってきたのですが、高速化の技術とか考え方がまだまだですね。
差分だけを計算するところで高速化できる。このメソッドは色々な問題でも使えそうだなと感じました。
解説にも載っていたのですが、区間の右端を1つ動かしたときに、条件を満たすように左端を右に動かして調整するアルゴリズムを尺取り法というらしいです。
個人的には辞書型が全然使いこなせていないというか、理解が浅いなと気づかされました。どんどん使って、理解を深めていきたいです。