問題概要
問題ページ
-
C - Colorful Candies
問題ページへ移動する
問題文
\(N\) 個のキャンディが左右一列に並んでいます。
それぞれのキャンディは、色 \(1\)、色 \(2\)、\(\ldots\)、色 \(10^9\)の、\(10^9\) 種類の色のうちいずれかの色をしています。
\(i = 1, 2, \ldots, N\) について、左から \(i\) 番目のキャンディの色は色 \(c_i\) です。
高橋君は並んでいるキャンディのうち、連続して並んだ \(K\) 個のキャンディをもらうことができます。
すなわち、\(1 \leq i \leq N-K+1\) を満たす整数 \(i\) を選んで、
左から \(i\) 番目、\(i+1\) 番目、\(i+2\) 番目、\(\ldots\)、\(i+K-1\) 番目のキャンディをもらうことができます。
高橋君はいろいろな色のキャンディを食べたいので、
もらうキャンディに含まれる色の種類数が多いほどうれしい気持ちになります。
高橋君がもらうキャンディに含まれる色の種類数の最大値を出力してください。
制約
- \(1 \leq K \leq N \leq 3 \times 10^5\)
- \(1 \leq c_i \leq 10^9\)
- 入力はすべて整数
問題の考察
ACコード
import sys
import collections
def solve():
input = sys.stdin.readline
mod = 10 ** 9 + 7
n, k = list(map(int, input().rstrip('\n').split()))
c = list(map(int, input().rstrip('\n').split()))
d = collections.defaultdict(int)
mx = 0
cnt = 0
for i in range(n):
if i >= k:
d[c[i-k]] -= 1
if d[c[i-k]] == 0:
cnt -= 1
if d[c[i]] == 0:
cnt += 1
mx = max(mx, cnt)
d[c[i]] += 1
print(mx)
if __name__ == '__main__':
solve()