クルトンのプログラミング教室

Pythonの使い方やPythonを使った競技プログラミングの解法などを解説しています。

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で書き直したものとなっています。

入力

P\\a_1\,…\,a_P

入力例



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)