[Python] 2部グラフ ABC210C

ABC210C

問題文通りの全探索を実装すると、計算量は$O(K(N-K+1))$でありTLE。
連想配列を用いたしゃくとり法をすれば、$O(N\log N)$

サンプルコード

from collections import Counter

N, K = map(int, input().split())
C = list(map(int, input().split()))
counter = Counter(C[:K])  # 最初のK個の連想配列
ans = len(counter)  # 最初のK個の種類数
for i in range(K, N):
    left = C[i - K]  #  1回目が K - K = 0（一番左）になるようにします
    right = C[i]
    counter[left] -= 1
    counter[right] += 1
    if counter[left] == 0:
        del counter[left]  # 0個でもlenで数えられてしまうので、delで消します
    ans = max(ans, len(counter))  #  現在の種類数で答えを更新します
print(ans)

時間は掛ったが、しゃくとり法や連想配列という意識なく、模範解答通りのアルゴリズムには辿り着いた。しかし試験時間の制約でデバッグ出来ずにTLEで終わった。
結構精神的ダメージを負ったが、その分、頭に刻み込まれたと思う。