Codeforce #521 Div3 D. Cutting Out

문제 원본

---

문제 설명

배열 S가 주어 졌을 때 길이가 k인 S의 부분 배열 t를 이용해 원소를 제거할 때 가장 많은 시간을 수 행 할 수 있는 부분 배열 t를 구하는 문제

ex

7개의 S배열 원소 3개의 부분 배열의 원소 개수

S = [1,2,3,2,4,3,1]

일 때 부분 배열 [1,2,3]일 때

2 번의 수행 시간동안 배열을 지울 수 있다.

1 번째 수행 때 S배열이 [1,3,2,4]가된다.

2 번째 수행 때 S배열이 [4]가된다.

3 번째 수행 하려고 할 때 S배열에 부분 배열 t가 존재 하지 않으므로 2번의 수행 시간이 걸린다.

---

문제 풀이

parametric search를 이용한 분제

1 step

    S배열의 각 원소의 개수를 구한다.

    위 예에선

    1 : 2개

    2 : 2개

    3 : 2개

    4 : 1개

 2 step

    원소의 개수를 오름차순으로 정렬한다.

3 step

    x번 시간으로 답을 구할 수 있는 질의를 parametric search(이분 탐색)을 이용하여 질의한다.

    x의 번위는 1개에서 S배열의 길이 만큼이다.

    질의 하는 함수는

    원소의 개수로 정렬된 배열을 이용하여 구한다.

    각 배열의 원소가 x개가 되는 원소의 리스트를 구한다.

    만약 x개가 되는 원소가 부분 배열의 개수 K개만큼 존재 한다면 Ture를 리턴한고 만들 수 없다면 False를 리턴한다.

    

    다시 parametric search로 돌아와서 질의 했을때 x를 만들 수 있다면 답의 구간을 앞쪽으로 옮기고 구할 수 없다면 답의 구간을 뒤로 옮긴다.

    구간이 앞이라는 뜻은 위의 예에서 1 ~ 7 구간에서 1 ~ 3, 5 ~ 7두개의 구간이 있다. 여기서 x=4일때 True를 리턴받는 다면 답이 5~7까지에 있다고 가정 할 수 있다.

---

소스 코드