<div id="readability-page-1" class="page"><div><p>문제 및 채점: <a href="https://oj.uz/problem/view/IOI20_tickets" target="_blank" rel="noopener">oj.uz</a></p>

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

<p>우선, 각 라운드에서 $S$ 값을 계산할 때 문제에서 정의한 방법 말고 쉬운 계산 방법을 찾아야 한다. 한 라운드에서 뽑힌 티켓들에 적힌 수를 $a_1, a_2, \dots, a_N$ $(a_1 \leq a_2 \leq \cdots \leq a_N)$이라고 하자. $S$ 값은 다음과 같이 간단하게 구할 수 있다.</p>
<p>$$S = a_N + a_{N-1} + \cdots + a_{\frac{N}{2}+1} - a_{\frac{N}{2}} - \cdots - a_1$$</p>
<p>즉, 라운드에서 뽑힌 티켓 중에 적힌 수가 큰 편에 속하는 수들은 $S$ 값에 더해지고, 작은 편에 속하는 수들은 $S$ 값에서 빼진다.</p>

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

<p>$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$의 합의 최대값을 구할 수 있다.</p>

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

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

</div></div>

PS 이야기

문제 및 채점: 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;
}

IOI2020 Day1 tickets 풀이

댓글