0
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

More than 3 years have passed since last update.

[Python] 2部グラフ ABC210C

Last updated at Posted at 2021-07-18

#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で終わった。
結構精神的ダメージを負ったが、その分、頭に刻み込まれたと思う。

0
0
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
0
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?