Edit

【pythonでABC210を解説】C - Colorful Candies

問題概要

問題ページ

C - Colorful Candies
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()

-Edit