IOI2020 Day1 tickets 풀이

문제 및 채점: 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)$이다.

 

#include <bits/stdc++.h> #include "tickets.h" using namespace std; #define mt make_tuple typedef pair<int, int> pii; typedef tuple<int, int, int> tiii; typedef long long lld; lld find_maximum(int K, vector<vector<int>> A) { int N = A.size(); int M = A[0].size(); lld ans = 0; vector<vector<int>> answer(N, vector<int>(M, -1)); vector <tiii> order; for (int i=0;i<N;i++){ for (int k=0;k<K;k++) ans -= A[i][k]; for (int k=1;k<=K;k++) order.push_back(mt(A[i][M-k]+A[i][K-k], i, M-k)); } sort(order.begin(), order.end()); vector <int> cnt(N, 0), lpt(N, 0); for (int i=1;i<=K*N/2;i++){ auto [v, p, q] = order[order.size()-i]; ans += v; cnt[p]++; } for (int k=0;k<K;k++){ vector <pii> arr; for (int i=0;i<N;i++) arr.push_back({-cnt[i], i}); sort(arr.begin(), arr.end()); for (int i=0;i<N/2;i++){ int t = arr[i].second; assert(cnt[t] > 0); answer[t][M-cnt[t]] = k; cnt[t]--; } for (int i=N/2;i<N;i++){ int t = arr[i].second; answer[t][lpt[t]++] = k; } } allocate_tickets(answer); return ans; }