BOJ 19935 Carnival Tickets

Carnival Tickets (IOI 2020 Day 1 #3)

 

 

 

문제 설명

- $n$가지 색의 티켓이 각 색마다 $m$개씩 존재하며, 티켓에는 각각 하나의 정수가 쓰여있다.

- $k$회의 라운드 동안, 각 라운드마다 하나의 색에서 하나의 카드를 선택하여 카드에 대해 점수를 받는다. 뽑은 카드에 적힌 숫자들을 크기 순서대로 $A_{1}$, $A_{2}$, $\cdots$ , $A_{n}$이라고 하자.

- 마스터 또한 카드 한 장을 뽑는다. 마스터가 뽑은 카드에 적힌 수가 $b$라고 하면, $\sum \left\vert A_{i} - b \right\vert$이 이번 라운드에 얻게 되는 점수이다.

- 각 라운드가 끝날떄마다 라운드에서 사용된 카드는 버려진다.

- 마스터는 각 라운드마다 점수가 최소화되도록 $b$를 뽑는다.

- 가장 많은 점수를 얻을 수 있도록 각 라운드마다 고르는 카드를 선택하자.

 

 

 

필요한 관찰

 

- 획득하는 점수

뽑은 카드에 적힌 숫자들을 크기 순서대로 $A_{1}$, $A_{2}$, $\cdots$ , $A_{n}$이라고 하자.

마스터가 항상 최적의 $b$를 선택하므로, 획득하는 점수는 $(A_{n} + A_{n-1} + \cdots + A_{\frac{n}{2}+1} - A_{\frac{n}{2}} - \cdots - A_{2} - A_{1})$이 된다.

 

 

 

티켓 고르기

 

전체 티켓 $nm$개 중, 점수가 더해지는 티켓 $\frac{nk}{2}$개와, 점수가 차감되는 티켓 $\frac{nk}{2}$개를 고르개 된다. (이상 점수가 더해지는 티켓을 P 티켓, 차감되는 티켓을 Q 티켓이라고 하자.)

또한, 한 종류의 색에서는 정확히 $k$개의 티켓을 골라야 한다.

 

 

- 어떻게 고를 것인가?

점수의 초기값은 $S = -\sum_{i = 0}^{n-1} \sum_{j = 0}^{k-1}x_{i, j}$으로 놓자. (처음에는 모든 티켓이 Q 티켓)

이제 Q 티켓 중 $\frac{nk}{2}$개를 P 티켓으로 교체해야 한다.

우선 max heap에 $ \left( x_{i, k-1}+x_{i, m-1} \right) $들을 모두 추가한다.

다음의 과정을 $\frac{nk}{2}$회 반복한다:

  - max heap에서 최댓값을 확인한다. (이를 $ \left( x_{i, j}+x_{i, j+m-k} \right) $라고 하자.) 이것의 의미는 Q 티켓에서 $(i, j)$ 티켓을 삭제하고, P 티켓에 $(i, j+m-k)$ 티켓을 추가한다는 뜻이다.

  - 확인한 최댓값을 S에 더해주고 pop한다.

  - max heap에 $ \left( x_{i, j-1}+x_{i, j+m-k-1} \right) $를 추가한다. 만약 $j = 0$이라면, 색 $i$에서 $k$개의 티켓을 전부 확정한 것이기 때문에 추가하지 않는다.

 

위의 프로세스로 티켓을 고르는 것은

  - 한 종류의 티켓 당 $k$개의 티켓 선택

  - 총 P 티켓의 개수와 Q 티켓의 개수가 각각 $\frac{nk}{2}$

의 조건을 만족하도록 티켓을 고른 경우 중 점수가 최대가 되는 경우임이 자명하다.

또한, P 티켓 중 최솟값은 Q 티켓 중 최댓값보다 항상 크다. 만약 아니라면, 해당 두 티켓을 바꿔주면 S가 증가하게 되므로 모순이다.

 

 

 

티켓 배치하기

 

이제 티켓을 배치하여야 한다.

위와 같이 티켓을 고르면 항상 티켓을 올바르게 배치하는 방법이 있을까?

 

Lemma 1. 위와 같이 티켓을 고르면 항상 티켓을 배치하는 방법이 있다.

Proof. 색 $i$의 티켓 중 P 티켓의 수를 $P_{i}$라고 하자.

각 라운드에서는 $P_{i}$가 큰 순서대로 $\frac{n}{2}$개의 색을 골라서 이 색들에서 P 티켓을 뽑고, 나머지 색은 Q 티켓을 뽑는다.

이후, 사용한 티켓을 삭제한다. $P_{i}$도 같이 갱신해준다.

이렇게 배치한다면 항상 한 라운드에 $\frac{n}{2}$개의 P 티켓과 $\frac{n}{2}$개의 Q 티켓을 각 색에서 하나씩 배치할 수 있다.

비둘기집의 원리와 수학적 귀납법에 의하여 증명된다.