CCO 2019 Shopping Plans

https://www.acmicpc.net/problem/19616

모든 상태를 중 가중치가 가장 작은 $K$ 개를 탐색할 때 좋은 전략은, 상태 전이 그래프를 Heap과 같이 구성하는 것입니다. 몇 가지 특수 케이스를 탐색해 보고 전체 문제로 확장시켜 봅시다.

$M = 1, x_1 = 0, y_1 = N$, 제곱 풀이

우리는 모든 가능한 $2^N$ 개의 집합 중 가중치가 가장 작은 $K$ 개를 탐색해야 합니다. 탐색 트리를 만드는데, 만약에

• 모든 상태가 가능한 집합에 일대일 대응되고
• 상태 $X$ 의 자식은 항상 현재 상태 이상의 가중치를 가지며
• 전이가 트리의 형태를 띈다

라고 하면, 루트 상태를 먼저 우선순위 큐에 넣은 후, 큐에서 현재 상태를 빼고, 현재 상태의 "자식 상태" 를 넣는 식으로 모든 가능한 경우를 탐색할 수 있습니다. 결국 모든 상태를 탐색하는 것은 백트래킹을 한다는 것이랑 동일하니, 위 조건을 만족하는 좋은 백트래킹 구조를 만들어 주면, 다항 시간 풀이를 찾을 수 있습니다. 예를 들어, $dfs(i, S) = $ ($i$ 번 까지 고려했고, 현재 고른 집합이 $S$ 임) 은 우리가 원하는 좋은 상태가 아닙니다. $(i, S)$ 와 같이 여러 상태가 한 집합에 대응되어서, 한 상태를 여러번 방문하기 때문입니다.

$S$ 의 원소 번호를 증가하는 수열 $[s_1, s_2, \ldots, s_k]$ 으로 두고, 수열을 한 원소씩 채워나가면서 백트래킹 해 봅시다. 이 때

• 각 수열은 집합에 당연히 일대일 대응되고
• 부모를 $[s_1, s_2, \ldots, s_{k-1}]$ 로 두면 부모의 가중치가 자신의 가중치보다 항상 작으며
• 트리의 형태로 구성됨

이라는 성질을 가집니다. 이제 Priority Queue의 노드에 $s_k$ 의 인덱스와 현재 가중치 합을 넣으면, 현재 수열의 뒤에 $s_k + 1, s_k + 2, \ldots, N$ ... 을 하나씩 넣어 보는 식으로 전이를 해 줄 수 있어서, 문제가 $O(KN \log N)$ 에 풀립니다.

$M = 1, x_1 = 0, y_1 = N$

이를 최적화하기 위해서는, 한 노드의 자식 상태는 구간 $L \le i \le R$ 에 대해서 $S + a_i$ 형태임을 관찰합시다. 모든 $L \le i \le R$ 에 대해서 이를 넣는 대신, $S + a_L - X$ 를 넣어준 후, $S + a_L - X$ 가 우선순위 큐에서 빠지는 시점에 (현재 답) + $a_{L+1} - a_L$ 을 넣는 식으로 이를 Lazy하게 처리해 주면, 한 노드에서 새롭게 생성되는 노드가 $O(1)$ 개로 줄어들어서 문제가 $O((N + K) \log N)$ 정도에 해결됩니다. 여담으로 아마 이게 2017년 선발고사 문제 중 하나였습니다.

$M = 1$

사실 위 풀이에서 $y_1 = N$ 이라는 조건은 집합의 크기를 같이 넣어주면 쉽게 없앨 수 있습니다. $x_1 = 0$ 이라는 조건을 없애고 문제를 해결해 봅시다.

$x_1 = 3$ 이라고 했을 때, 최소의 답은 ${1, 2, 3}$, 그 다음 최소의 답은 ${1, 2, 4}$, 그 다음 최소는 ${1, 2, 5}$ 아니면 ${1, 3,4}$ ... 와 같은 식으로 전파될 것입니다. 기본적으로 ${1, 2, 3}$ 을 갖고 가는 것에서 시작하지만, 만약에 대체가 일어난다면 뒤쪽부터 먼저 대체가 되는 모습을 볼 수 있습니다.

각 집합에 일대일 대응되는 대체 수열 $[s_1, s_2, \ldots, s_k]$ 를 정의합시다. 대체 수열은 감소 수열이고 ($s_1 > s_2 > \ldots > s_k$), $1 \le i \le x_1$일 경우 $s_i \ge x_1 - i + 2$ 이 항상 만족됩니다. 만약 $k < x_1$ 일 경우 $S = {s_1, s_2, \ldots, s_k, x_1 - k + 1, x_1 - k + 2 \ldots, 1}$ 과 같이 구성되어 있고, 그 외의 경우 대체 수열 자체가 집합에 대응됩니다. 이 때 역시도

• 각 수열은 집합에 일대일 대응되고
• 부모를 $[s_1, s_2, \ldots, s_{k-1}]$ 로 두면 부모의 가중치가 자신의 가중치보다 항상 작으며
• 트리의 형태로 구성됨

이 모두 만족하는 것을 알 수 있습니다. 고로 대체 수열에 대해서 탐색을 하면 문제가 $O(KN \log N)$ 에 해결됩니다. 위에서 사용했던 것과 똑같은 최적화 법을 사용하면 $O((K + N) \log N)$ 으로 최적화 할 수 있습니다.

$x_i = y_i = 1$

$M > 1$ 인 경우를 해결할 때의 전략은, 각 집합에 대해서 유의미한 부분집합의 개수가 많지 않을 테니 (너무 크기가 큰 부분집합은 고려하지 않아도 될 테니), 각 집합에 대해서 적당한 개수의 작은 부분집합을 나열하고, $x_i = y_i = 1$ 인 케이스로 환원하여 전체 문제를 해결하는 것입니다. 이는 USACO에 예전에 나온 Robotic Cow Herd라는 문제와 동일합니다. 크게 두가지 방법으로 풀 수 있는데

• 위에서 말한 대로 상태 전이 그래프를 Heap의 형태로 잘 설계해서 해결할 수 있습니다. 어렵지 않으니 한번 연습 삼아 해 보는 것을 추천합니다. 물론 전 안 해봤습니다.
• 이 문제를 $K$번째 최단 경로 문제로 모델링할 수 있습니다. $i$번 집합의 각 원소를 $(i-1) \rightarrow i$ 로 가는 간선의 가중치로 두면 (중복 간선을 집합 원소만큼 만듭니다) 결국 문제는 $0 \rightarrow N$ 으로 가는 $K$ 번째 최단 경로를 찾는 문제입니다. 이는 BOJ 20536 남부순환로 처럼 Eppstein's K-th shortest path algorithm을 사용하면 됩니다. (풀이)

전체 문제, 제곱 풀이

각 집합에 대해서 가장 작은 $K$ 개의 부분 집합을 나열합시다. $K+1$ 번째로 큰 부분 집합은 고려할 일이 없으니, 신경쓰지 않아도 됩니다. 이제 모든 집합에 대해서 이 부분집합 중 하나를 골라야 하니, $x_i = y_i = 1$ 인 경우로 환원이 되었습니다. $O(MK)$ 개의 간선이 있으니 $O(MK \log N)$ 입니다.

전체 문제

각 집합에 대해서, 최소 집합 (${1, 2, \ldots, x_i}$) 은 무조건 먹어야 하는 집합이라고 생각하고, 전체 답에 더해줍시다. 이 경우 각 집합에 대해서 가장 작은 후보의 값은 항상 0입니다. 이제 탐색을 전역적으로 수행해서, 가장 작은 후보를 제외한 후보가 $K$ 개 나올때까지 탐색해 줍니다. 만약 여기서 $K+1$ 번째 뒤로 나온 후보가 답의 일부가 된다면, 이보다 작은 후보를 $K$ 개 찾을 수 있으니 모순입니다. 이렇게 하면 각 집합을 매번 탐색하지 않고, 같은 Priority Queue를 공유하면서 한번에 필요한 것만 전부 탐색해 줄 수 있습니다. 이렇게 하면 $O(M + K)$ 개의 간선이 있으니 $O((M + K) \log N)$ 입니다.

알아두면 좋은 정보

• 이러한 식의 검색 테크닉을 Fracturing Search라고 하나 봅니다. 이 동영상에서는 저랑 설명하는 방식이 다른데, 비슷한 이야기 같습니다.
• 전 BOJ 20536 남부순환로 문제의 풀이를 토대로 생각하니까 도움이 많이 되었습니다. 문제 자체를 날먹하는 데도 약간 도움이 됩니다.