AtCoder Beginner Contest 210 C - Colorful Candies【Python】
https://atcoder.jp/contests/abc210/tasks/abc210_c
AtCoder ProblemsのRecommendationで Difficulty: 359、Solve Probability: 47%でした。
間に合うと思って単純に実装したところTLEとなり、解説を見て実装するもWAとなってしまったため他の方の提出コードを見ました。単純な実装では計算量がO(K(N−K+1))でO(NK)になるとのことですが、計算量の求め方がよくわかってないですね。
実際に計算してみたところ、Nが制約の最大でKがその半分の値の場合は2 * 10 **10程度になり実行時間制限を超えるようだというのはわかりました。
尺取り法を使う他の問題も解いていきたいところです。
https://qiita.com/u2dayo/items/0ae64fdedf3535aefe83 https://atcoder.jp/contests/abc210/submissions/27478365 https://atcoder.jp/contests/abc210/submissions/27598182
from collections import defaultdict N, K = map(int, input().split()) C = list(map(int, input().split())) d = defaultdict(int) ans = 0 now = 0 for i in range(N): new_val = C[i] d[new_val] += 1 if d[new_val] == 1: now += 1 if i >= K: old_val = C[i - K] d[old_val] -= 1 if d[old_val] == 0: now -= 1 ans = max(ans, now) print(ans)