[伯俊]#2531回転寿司

質問する

回転寿司レストランは回転するベルトの上で、皿の中でいろいろな寿司を盛って、客はその中から自分の好きな寿司を選んで食べます.寿司の種類を数字で表す場合、下図は回転寿司レストランのベルト状態の例を示しています.ベルトには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以下の整数が各行に与えられる.

しゅつりょく

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

入力例1

8 30 4 30
7
9
7
30
2
7
9
25

サンプル出力1

5

入力例2

8 50 4 7
2
7
9
25
7
9
7
30

サンプル出力2

4

に答える

この問題はハッシュマップを用いてスライドウィンドウを実現し,二重ポインタを用いてウィンドウを移動し,対応するウィンドウ内で寿司の個数を探すことで答えを見つけることができる.

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.HashMap;

public class Main {

    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] input = br.readLine().split(" ");
        int N = Integer.parseInt(input[0]);
        int d = Integer.parseInt(input[1]);
        int k = Integer.parseInt(input[2]);
        int c = Integer.parseInt(input[3]);

        HashMap<Integer, Integer> window = new HashMap<>();     //해쉬맵을 이용해서 크기가 k인 슬라이딩 윈도우 생성

        int[] arr = new int[N];
        for(int i=0; i<N; i++)
            arr[i] = Integer.parseInt(br.readLine());

        int left = 0;
        int right = 0;
        while(right<k) {              //첫 윈도우 생성
            int num = arr[right];
            if(window.containsKey(num))
                window.put(num, window.get(num)+1);
            else
                window.put(num, 1);
            right++;
        }

        int max = 0;

        while(left<N) {
            if(window.containsKey(c)) {       //각 경우 마다 최대 음식 수 체크
                max = Math.max(window.size(), max);
            }
            else {
                max = Math.max(window.size()+1, max);
            }

            int l = arr[left++];      //투 포인터 이용해서 윈도우에 초밥 넣고 
            int r = arr[right++];

            if(window.get(l)==1)
                window.remove(l);
            else
                window.put(l, window.get(l)-1);

            if(window.containsKey(r))
                window.put(r, window.get(r)+1);
            else
                window.put(r, 1);

            if(right==N)
                right=0;
        }

        System.out.println(max);
    }
}