티스토리 뷰

IOI/IOI2020

IOI2020 Day1 tickets 풀이

전명우 2020. 9. 22. 21:11

문제 및 채점: oj.uz

 

티켓은 $N$ 개의 색 중 한 가지 색을 띄며, 각 색마다 $M$ 개의 티켓이 있다. 티켓에는 수가 적혀있는데, 티켓에 적힌 수는 서로 다를 수 있다. $K$ 번의 라운드를 진행할거고 각 라운드마다 $N$ 개의 서로 다른 색의 티켓을 뽑고, 어떤 수 $b$를 임의로 정해 $b$와 $N$ 개의 티켓에 적힌 수와 차이값을 구해 모두 더한 값을 $S$라 하자. 이때, $S$의 값이 최소가 되도록 수 $b$를 정한다. 한 라운드에 쓰인 티켓은 소멸되기 때문에 한 티켓은 최대 한 라운드에서만 사용 가능하다. 각 라운드마다 티켓을 적절히 골라 모든 라운드의 $S$ 값들을 다 더한 값을 최대화하는 문제다. 편의상 $N$은 짝수다.

 

우선, 각 라운드에서 $S$ 값을 계산할 때 문제에서 정의한 방법 말고 쉬운 계산 방법을 찾아야 한다. 한 라운드에서 뽑힌 티켓들에 적힌 수를 $a_1, a_2, \dots, a_N$ $(a_1 \leq a_2 \leq \cdots \leq a_N)$이라고 하자. $S$ 값은 다음과 같이 간단하게 구할 수 있다.

$$S = a_N + a_{N-1} + \cdots + a_{\frac{N}{2}+1} - a_{\frac{N}{2}} - \cdots - a_1$$

즉, 라운드에서 뽑힌 티켓 중에 적힌 수가 큰 편에 속하는 수들은 $S$ 값에 더해지고, 작은 편에 속하는 수들은 $S$ 값에서 빼진다.

 

$i$ 번 색을 띄는 티켓 $M$ 개 중에 $g_i$ 개의 티켓이 라운드에서 큰 편에 속했다고 하면, $K-g_i$ 개의 티켓이 라운드에서 작은 편에 속했다. 또한 $S$의 합이 최대화 되기 위해서는 티켓 $M$ 개 중에 적힌 수가 큰 상위 $g_i$ 개의 티켓이 뽑혀야 되고, 적힌 수가 작은 하위 $K-g_i$ 개의 티켓이 뽑혀야 된다. 그리고 $g_i \leq K$ 이며, $g_i$의 합은 $\frac{NK}{2}$가 되어야 한다.

 

$1 \leq i \leq N$인 모든 $i$에 대해 $S$의 합이 최대가 되는 $g_i$를 욕심쟁이 기법으로 구할 것이다. 우선 처음에 모든 $g_i$가 $0$이라고 하고, $i$ 번 색의 $j$ 번째 티켓에 적힌 수를 $A[i][j]$라고 하자. ($A[i][j] \leq A[i][j+1]$) 그러면 $S$의 합의 초기값은 $-A[i][1]-A[i][2]-\cdots-A[i][K]$의 합이 된다. 이제 $g_i$를 적절히 증가시켜 $g_i$의 합을 $\frac{NK}{2}$로 만들 것이다. $g_i$의 값을 1 증가하면, $S$의 합은 $A[i][g_i+1]+A[i][K-g_i]$ 만큼 증가하게 된다. $S$의 합이 최대한 증가하도록 매 순간 증가량이 가장 크도록 $g_i$ 값을 1씩 증가시켜주면 $S$의 합의 최대값을 구할 수 있다.

 

이제 구체적으로 뽑힌 티켓이 어떤 라운드에 뽑혔는지 구하는 문제가 남았다. 라운드에서 작은 편에 속하는 수들은 라운드에서 큰 편에 속하는 수들보다 크지 않은 점을 이용하여 이 문제 또한 욕심쟁이 기법으로 해결할 수 있다.

 

이 문제를 해결하는 시간복잡도는 $O(NK \lg NK)$이다.

 

더보기

'IOI > IOI2020' 카테고리의 다른 글

IOI2020 Day2 mushrooms 풀이  (0) 2020.09.24
IOI2020 Day2 biscuits 풀이  (0) 2020.09.23
IOI2020 Day2 stations 풀이  (0) 2020.09.23
IOI2020 Day1 plants 풀이  (0) 2020.09.22
IOI2020 Day1 tickets 풀이  (0) 2020.09.22
IOI2020 Day1 supertrees 풀이  (0) 2020.09.22
댓글
댓글쓰기 폼