Pythonで理解する蟻本「3-2 Jessica's Reading Problems(POJ No.3320)」(p.137)
この記事は「プログラミングコンテストチャレンジブック第2版」(蟻本)の
「3-2 Jessica's Reading Problems(POJ No.3320)」(p.137)
のコードをPythonで書き直したものとなっています。
入力
入力例
5
1 8 8 8 1
解答
# 入力 P = int(input()) a = list(map(int,input().split())) # 書かれている事柄の総数を計算 ALL = set(a) n = len(ALL) # しゃくとり法により解を求める s = 0 t = 0 num = 0 count = {} # 事柄→出現数の対応 res = P while True: while t < P and num < n: if not a[t] in count: # 新しい事象が出現 count[a[t]] = 0 num += 1 count[a[t]] += 1 t += 1 if num < n: break res = min(res, t - s) count[a[s]] -= 1 if count[a[s]] == 0: # ある事柄の出現数が0になった num -= 1 s += 1 print(res)