IOI 2020 day1 - Carnival Tickets

문제 링크 : www.acmicpc.net/problem/19935

문제 소개

k 판의 게임을 진행한다. 각각의 게임은 m개의 숫자카드중 일부가 있는 n개의 카드 세트에서 1개씩을 뽑는다. 주최측이 원하는대로 수를 선정하고, 그 수와 뽑은 n개의 수의 차이의 절댓값 만큼 점수를 얻는다. 이때 주최측은 얻는 점수가 최소화 되도록 수를 선정한다. 이때 k 판을 진행하면서 얻는 점수가 최대가 되도록 각 판에서 뽑을 숫자카드를 설정하고, 이때 얻을 점수를 구하여라. 

문제 풀이(+의식의 흐름)

part 1. 문제를 읽으면서 생각한 것들 - 1차 생각, 해야할 일들 정리

이 문제를 시작한 이유. 1분 보고 나서 DP 느낌이 확 왔다. 뭔가 난이도의 대부분은 관찰이고, 구현은 그렇게 어렵지 않을 것 같다는 생각이 크게 들었다.

일단 n개의 숫자가 있으면 주최측이 고를 수는 크기 순서대로 n/2번째에 해당하는 수를 고를 것이다. 이는 조금만 생각해도 그 값이 최솟값이라는 것을 알 수 있다. 여러가지 문제에서 사용하기도 해봤고, 수직선 위에서 생각하면 굉장히 직관적인 사실이다.
이를 통해서 한 게임에서 선택된 카드들이 있을 때 그 중 중간값을 구하고, 그 수로부터 차이를 모두 구해서 더하는 것으로 그 게임에서 얻을 점수를 구할 수 있게 되었다. 

part 2. 점수를 구하는 법

점수는 이 문제의 핵심이자 가장 중요한 부분이다. 하지만, 위의 형식은 너무나도 당연하고 단순하고 나에게 정보를 주지 않았다. 나는 이 문제가 애초에 DP라고 생각을 해봤기 때문에 위의 점수체계를 식으로 정리해보았다.
n개의 숫자중 가장 작은 숫자가 num[1], 가장 큰 숫자가 num[n]이라고 하자. 식은 아래와 같이 나온다.
(num[n/2]-num[1])+(num[n/2]-num[2])+(num[n/2]-num[2])....+(num[n-1]-num[n/2])+(num[n]-num[n/2])

오... 식을 써보니 몇가지 사실이 확실히 관찰되었다. 위의 값은 num[n/2]와는 큰 관련이 없었다. 절반의 경우에는 빼지고, 절반의 경우에는 더해지니까. 얻는 점수는 가장 큰 n/2개의 수의 합에서 가장 작은 n/2개의 수의 합을 뺀 것이다!

part 3. 2의 확장. (감과 증명)

근데 이것은 내가 어떤 숫자를 선택해야하는지에 큰 도움을 주지 않는다. 한 번의 게임에만 도움을 준다. 그래서 나는 여기서 한 가지 생각을 했다.
k판에 사용할 수들 nk개가 정해져 있으면, 가장 큰 nk/2 개를 항상 더하는 쪽에 사용할 수 있고, 가장 작은 nk/2 개를 항상 빼는 쪽에 사용할 것이라는 추측이다. 사실 몇 번의 경험과 진전이 없는 문제에 거의 확신을 가지고 있었다.

어쩌피 최종적으로 몇 라운드에 어떤 수 카드를 선정해야할지 모두 정해야 하기 때문에 nk개를 어떻게 나눠야 할지 생각을 해보았다.

n개의 세트에는 각각 ai개의 큰 그룹에 속하는 수와 bi개의 작은 그룹에 속해야 하는 수가 있을 것이다. 이때 n개의 세트를 ai가 큰 순서대로 정렬한다. 이 후 앞의 n/2개에서는 큰 그룹에서 선정하고, 뒤의 n/2개에서는 작은 그룹에서 선정한다. 그 숫자들을 모으면 앞에서 선정한 숫자들이 뒤에서 선정한 숫자들보다 크기 때문에, 앞에 선정한 숫자들이 더해지고, 뒤에 선정한 숫자들이 빼진다. 위와 같은 방식으로 k번을 반복하면 $O(NKlgN)$에 전체에서 큰 그룹의 nk/2개는 어떤 그룹의 큰 n/2개쪽에 속하게 할 수 있다.

part 4. k개를 선택하는 법

이제 우리가 해결해야할 문제는 n개의 그룹에서 각각 k개의 수들을 선택해서 전체 nk개 의 수 들 중에서 절반이 크게 절반이 작게 만들어야 한다.

위에서 설정했듯이 한 세트에서 ai개는 큰 그룹으로 선택될 것이고, bi개는 작은 그룹으로 선택될 것이다. 당연히 한 세트 내에서 가장 큰 ai개와 가장 작은 bi개를 선택할 것이고, 한 세트당 선택하는 수는 총 O(k)가지 경우가 나오게 된다.

조금 더 생각을 해보자. 모든 세트에서 가장 큰 k개를 선택해 놓는다. 당연히 우리는 이 k개 중 가장 작은 수 대신 세트의 가장 작은 수로 바꿔서 빼는 그룹에 넣을 것이다. 이 과정을 nk/2 번 반복하면 된다. 그리고 그 선택은 n개의 세트 중 바꿨을 때 가장 이득이 되는 세트에서 진행하는 것이 좋다. 같은 그룹에서는 맨 처음 선택하는 것이 가장 이득이기 때문에 이 문제를 위와 같이 greedy 적으로 해결할 수 있다.

part 5. 정리

1. n개의 각각의 세트에서 가장 큰 k개를 선택해 모두 더하는 그룹에 넣는다. 
2. 더하는 그룹에서 수 하나를 빼고, 빼는 그룹에 수 하나 넣는 것을 했을 때, n개의 세트에 대해서 각각 어느정도의 이득을 보는지 구한다.
3. 2번의 과정을 통해서 가장 큰 이득을 보는 세트에서 더하는 숫자를 하나 줄이고 빼는 숫자 하나를 늘리는 과정을 한다.
4. 위의 과정을 nk/2번 반복한다.
5. 4번 과정을 진행하면, 어떤 수 카드들을 선택해야 할지가 모두 정해지며, 이 과정에서 얻는 점수도 구할 수 있다.
6. 더할 숫자가 가장 많이 남은 n/2개의 그룹에서 더할 숫자를 뽑고, 나머지 n/2개의 그룹에서 뺄 숫자를 뽑는 과정으로 한 라운드에서 선택할 n개의 수를 정한다.
7. 6번의 과정을 k번 반복하여 nk의 수 카드에 대해서 어느 라운드에 선택할지를 모두 결정한다.

코드

#include "tickets.h"
#include<bits/stdc++.h>
using namespace std;
typedef int ll;
typedef pair<ll,ll> pii;

#define ff first
#define ss second
#define pb push_back

struct poi{
	ll a,b,idx;
};

ll fl[1010101];
ll fl2[1010101];
ll yak[1010101];


bool sf2(ll a,ll b){
    return fl[a]+fl2[a]<fl[b]+fl2[b];
}

std::vector<std::vector<ll>> arr;

struct sf{
	bool operator()(poi &a,poi &b){
		return arr[a.idx][a.a]+arr[a.idx][a.b]<arr[b.idx][b.a]+arr[b.idx][b.b];
	}
};

priority_queue<poi,vector<poi>,sf> pq;

long long find_maximum(ll k, std::vector<std::vector<ll>> x) {
	arr=x;
	ll n = x.size();
	ll m = x[0].size();
	long long ans=0;
	ll i,j,kk=k;
	std::vector<std::vector<int>> answer;
	for (int i = 0; i < n; i++) {
		std::vector<int> row(m);
		for (int j = 0; j < m; j++) {
			if (j < k) {
				ans-=arr[i][j];
				row[j] = j;
			} else {
				row[j] = -1;
			}
		}
		answer.push_back(row);
	}

	for(i=0;i<n;i++){
		fl[i]=k-1;
		poi x;
		x.a=k-1;
		x.b=x.a+m-k;
		x.idx=i;
		pq.push(x);
	}
	for(ll t=1;t<=n*k/2;t++){
		auto k=pq.top();
		pq.pop();
		ans+=arr[k.idx][k.a]+arr[k.idx][k.b];
		swap(answer[k.idx][k.a],answer[k.idx][k.b]);
        fl[k.idx]--;
		if(fl[k.idx]>=0){
			poi x;
			x.a=fl[k.idx];
			x.b=x.a+m-kk;
			x.idx=k.idx;
			pq.push(x);
		}

	}

    for(i=0;i<n;i++){
        yak[i]=i;
        fl2[i]=fl[i]+m-kk+1;
    }

    for(i=0;i<k;i++){
        sort(yak,yak+n,sf2);
        for(j=0;j<n/2;j++){
            answer[yak[j]][fl2[yak[j]]]=i;
            fl2[yak[j]]++;
        }
        for(j=n/2;j<n;j++){
            answer[yak[j]][fl[yak[j]]]=i;
            fl[yak[j]]--;
        }
    }


	allocate_tickets(answer);
	return ans;
}