훈련 프로그램 I

유명 FC온라인 클럽 "ACE"는 곧 있을 eSports 대회 예선을 대비하여 실력 향상을 위해 훈련 프로그램을 운영하고 있다. 클럽에는 $N$ 명의 선수가 있으며, 각 선수는 다양한 실력을 갖추고 있다. 다가올 예선에 대비하여, 선수들은 2인 1조 훈련팀을 구성하려고 한다. 각 선수는 정확히 두 개의 훈련팀에 참여해야 하며, 같은 두 선수로 이루어진 훈련팀이 두 번 등장해서는 안 된다.

실력이 $a$ 인 선수와 실력이 $b$ 인 선수 두 명이 훈련팀을 이루면, 해당 팀의 실력 불균형은 $|a-b|$ 이다. 실력 차이가 큰 팀은 서로 소통하고 전략을 공유하는 데 어려움을 겪을 수 있기 때문에, 모든 팀의 실력 불균형 총합을 최소화하는 것이 훈련 효율을 높이는 데 중요하다.

이 훈련 프로그램은 $Q$ 번 진행되는데, 회차마다 외부에서 초청 선수가 참여하여 진행한다. 선수 $N$ 명의 실력이 주어졌을 때, 초청된 선수의 실력까지 고려하여 훈련팀을 구성하고 모든 팀의 실력 불균형 총합을 최소화하는 프로그램을 작성하라.

입력 형식

첫 줄에 선수의 수를 나타내는 정수 $N$ 과 훈련 프로그램의 횟수를 나타내는 정수 $Q$ 가 공백으로 구분되어 주어진다. ( $2 \le N \le 100\,000;$ $1 \le Q \le 100\,000$ )

그다음 줄에 각 선수의 실력을 나타내는 $N$ 개의 정수가 공백으로 구분되어 주어진다. 이때, 주어지는 실력은 $1$ 이상 $1\,000\,000\,000$ 이하이다.

이어지는 $Q$ 개의 줄의 $i$ 번째 줄에는 $i$ 번째 훈련 프로그램에 초청된 선수의 정보를 나타내는 정수 $k$ 와 $k$ 개의 정수가 공백으로 구분되어 주어진다. 이는 $i$ 번째 훈련 프로그램에서 $k$ 명의 선수가 초청됨을 의미하며, 주어지는 $k$ 개의 정수는 초청된 선수의 실력을 나타낸다. 이때, $k$ 는 항상 $1$ 이며, 주어지는 실력은 $1$ 이상 $1\,000\,000\,000$ 이하이다.

출력 형식

$Q$ 개의 줄에 걸쳐 정답을 출력한다. 출력의 $i$ 번째 줄에 $i$ 번째 훈련 프로그램에서 모든 팀의 실력 불균형 총합의 최솟값을 출력한다.

예제

입력

6 2 7 7 8 5 4 5 1 9 1 5

출력

6 4

예제 설명

총 $6$ 명의 선수가 있으며, 선수의 실력은 각각 $7, 7, 8, 5, 4, 5$ 이다.

첫 번째 훈련 프로그램에서 실력이 $9$ 인 선수가 초청된다. 이 경우, 다음과 같이 훈련팀을 구성하면 모든 팀의 실력 불균형 총합이 $6$ 이 되며, 이보다 실력 불균형의 총합이 더 낮은 경우는 없다.

첫 번째 선수와 두 번째 선수가 훈련팀을 이루어 실력 불균형 $0$ 이 된다.
첫 번째 선수와 세 번째 선수가 훈련팀을 이루어 실력 불균형 $1$ 이 된다.
세 번째 선수와 초청 선수가 훈련팀을 이루어 실력 불균형 $1$ 이 된다.
두 번째 선수와 초청 선수가 훈련팀을 이루어 실력 불균형 $2$ 가 된다.
네 번째 선수와 다섯 번째 선수가 훈련팀을 이루어 실력 불균형 $1$ 이 된다.
네 번째 선수와 여섯 번째 선수가 훈련팀을 이루어 실력 불균형 $0$ 이 된다.
다섯 번째 선수와 여섯 번째 선수가 훈련팀을 이루어 실력 불균형 $1$ 이 된다.

두 번째 훈련 프로그램에서 실력이 $5$ 인 선수가 초청된다. 이 경우, 다음과 같이 훈련팀을 구성하면 모든 팀의 실력 불균형 총합이 $4$ 가 되며, 이보다 실력 불균형의 총합이 더 낮은 경우는 없다.

첫 번째 선수와 두 번째 선수가 훈련팀을 이루어 실력 불균형 $0$ 이 된다.
첫 번째 선수와 세 번째 선수가 훈련팀을 이루어 실력 불균형 $1$ 이 된다.
두 번째 선수와 세 번째 선수가 훈련팀을 이루어 실력 불균형 $1$ 이 된다.
네 번째 선수와 초청 선수가 훈련팀을 이루어 실력 불균형 $0$ 이 된다.
다섯 번째 선수와 초청 선수가 훈련팀을 이루어 실력 불균형 $1$ 이 된다.
다섯 번째 선수와 여섯 번째 선수가 훈련팀을 이루어 실력 불균형 $1$ 이 된다.
네 번째 선수와 여섯 번째 선수가 훈련팀을 이루어 실력 불균형 $0$ 이 된다.

채점 방식

입력 케이스들은 다음과 같은 종류로 구별되며, 한 종류의 케이스를 다 맞혀야 그 종류에 배정된 점수를 받을 수 있다.

종류 1: 27점

$N \le 8;$ $Q \le 5$

종류 2: 34점

$N, Q \le 1\,000$

종류 3: 39점

추가적인 제한 조건이 없음.

해설

훈련 프로그램이 한 번만 있고, 초청 선수가 없는 경우의 풀이에 대해 생각해보자.

$N$ 명의 선수들을 실력 순서대로 오름차순 정렬한다. 정렬한 상태에서 연속한 부분 배열을 그룹으로 묶어 그 그룹 안에 있는 사람들끼리 훈련팀을 만들면 모든 팀의 실력 불균형 총합을 최소화할 수 있다. 문제의 조건 중 같은 두 선수로 이루어진 훈련팀이 두 번 등장해서는 안 된다는 조건 때문에 이 그룹의 크기는 $3$ 이상이어야 한다.

또한, 그룹의 크기가 $6$ 이상인 경우 그룹을 크기가 $3$ 이상인 여러 그룹으로 나누어 실력 불균형 총합을 더 작게 만들 수 있다. 따라서, 최적의 그룹 크기는 $3$ 이상 $5$ 이하이다.

예를 들어, 그룹의 크기가 $4$ 이며 그룹 안에 있는 선수들의 실력이 오름차순으로 $a_1$ , $a_2$ , $a_3$ , $a_4$ 일 때, 이 그룹 안에서 훈련팀을 만들어 실력 불균형 총합을 가장 작게 만드는 경우, 실력 불균형 총합은 $2(a_4-a_1)$ 이다.

이 점을 이용하여 동적계획법(Dynamic Programming, DP)으로 문제를 해결할 수 있다. 아래 식에서 $A_i$ 는 실력 순서대로 오름차순 정렬했을 때 $i$ 번째 선수의 실력을 의미한다.

D_i = \text{첫 번째 선수부터 $i$ 번째 선수까지 훈련팀을 만들 때, 실력 불균형 총합의 최솟값}

\begin{equation*} D_i = \begin{cases} 0, & \text{if } i = 0 \\ \infty, & \text{if } i = 1 \text{ or } i = 2 \\ \min_{j=3}^{5} \left( D_{i-j} + 2(A_i - A_{i-j+1}) \right), & \text{if } i \geq 3 \end{cases} \end{equation*}

\text{최종 답: } D_N

맨 처음 정렬하는 데 $\mathcal{O}(N \lg N)$ 의 시간복잡도, DP는 $\mathcal{O}(N)$ 의 시간복잡도를 가진다.

$Q$ 번의 훈련 프로그램마다 $\mathcal{O}(N)$ 시간복잡도의 DP를 수행하는 경우, 총 시간복잡도는 $\mathcal{O}(QN + N \lg N)$ 으로 종류 1과 종류 2의 점수를 받을 수 있다.

각 훈련 프로그램마다 한 명의 초청 선수가 있으므로, 위와 비슷한 DP를 오른쪽에서 왼쪽으로 한 번 더 수행하여 $A$ 배열의 prefix와 suffix에 대한 DP 값을 미리 계산해 둔다. 새로 초청된 선수가 $A$ 배열의 어느 지점에 추가될지 이분탐색으로 계산하고, 미리 구한 prefix와 suffix의 DP 값을 이용하여 빠르게 답을 계산할 수 있다. 총 시간복잡도는 $\mathcal{O}((Q+N) \lg N)$ 이 된다.