[BOJ]2531回転寿司(Python)

質問する

回転寿司レストランは回転するベルトの上で、皿の中でいろいろな寿司を盛って、客はその中から自分の好きな寿司を選んで食べます.寿司の種類を数字で表す場合、下図は回転寿司レストランのベルト状態の例を示しています.ベルトには2種類以上の寿司があります.

新しくオープンした回転寿司店は、不況で営業が困難なため、以下の2つの活動で売上を伸ばしたいと考えています.
もともと回転寿司は客が勝手に寿司を選び、食べた寿司によって食事量を計算していたが、ベルトのいずれかの位置からk個の皿を連続して食べると、割引の固定価格で提供された.
お客様1人につき1種類の寿司が書かれたクーポンを配布し、1番のイベントに参加する際に、そのクーポンに書かれた寿司を無料でプレゼントします.この番号に書いてある寿司が今ベルトにない場合、コックはお客様に作り直します.
以上の割引イベントに参加して、できるだけいろいろな寿司を食べます.図の例を取って考えなさい.k=4、クーポンとして30番寿司を受け取ったとします.クーポンを考えなければ4種類の異なるお寿司(9、7、30、2)、(30、2、7、9、25)、(2、7、9、25)の3種類を食べることができ、30番のお寿司をクーポンに加えれば(2、7、9、25)、5種類のお寿司を食べることができます.
回転寿司店のベルト状態、メニュー上の寿司の種類数、連続して食べる皿の数、クーポン番号を取得するプログラムを作成し、お客様が食べられる寿司の種類の最低価格を取得します.

入力

1列目は回転寿司ベルトに乗せた皿の数N、寿司の種類数d、連続して食べる皿の数k、クーポン番号cの間にそれぞれスペースを残します.しかし,2≦N≦30000,2≦d≦3000,2≦k≦3000(k≦N),1≦c≦dであった.2行目からN行目では、ベルトの1つの位置から回転方向に沿って歩くと、寿司の種類を表す1以上d以下の整数が各行に与えられる.

しゅつりょく

与えられた回転寿司ベルトにおいて、食べられる寿司の種類数の最値は整数として出力される.

例

입력
8 30 4 30
7
9
7
30
2
7
9
25

출력
5

コード#コード#

N, d, k, c = map(int, input().split())
sushi = [int(input()) for _ in range(N)]
sushi += sushi[:k-1]

ans = 0
for i in range(N):
    eat = set(sushi[i:i+k] + [c])
    ans = max(ans, len(eat))

print(ans)

ポスト