Yukicoder No. 119 旅行のツアーの問題

Yukicoder No. 119 여행 문제

문제 링크

문제

$N$ 개의 나라가 있습니다.

나라는 $0$번부터 $N-1$번까지 번호가 붙어있습니다.

A군은 $N$개의 나라 중 방문하고 싶은 나라를 골랐습니다.

A군은 반드시 번호가 작은 나라부터 차례로 방문을 합니다.

 

여행사에는 각 나라별로 $1$개씩의 여행 패키지가 있습니다.

여행 패키지에 참여하는 게 좋을 때도 있지만

자유도가 줄어들어서 싫을 때도 있습니다.

여행 패키지에 참여할 때와, 참여하지 않을 때의 만족도가 정해져 있습니다.

 

또한, 여행사 직원의 말은, "한 나라의 여행 패키지에 참여하면, 다른 나라의 여행 패키지에도 참여해야 한다."

같은 조건이 있는 경우도 있다고 합니다.

예를 들면,

• $x$번 나라의 여행 패키지에 참여하면, $y$번 나라의 여행 패키지에도 참여해야 한다. ($x <y$)

와 같은 조건입니다.

$x$번 나라와 $y$번 나라, 양쪽 모두 방문하는 경우 해당 조건이 생깁니다.

A군은 이유는 잘 모르겠지만, 조건을 받아들이기로 했습니다.

A군의 총 만족도는, 방문한 나라의 만족도의 합입니다.

A군은 총 만족도를 최대화 하고 싶습니다.

최대의 총 만족도를 구해주세요.

 

즉, 각각의 나라에 대해 살펴보면

• $x$번 나라에 방문하지 않는다.
• $x$번 나라에 방문하지만, 여행 패키지에 참여하지 않는다.
• $x$번 나라에 방문하고, 여행 패키지에 참여한다.

중 하나를 선택해야 합니다.

입력

자세한 입력 형식은, 원문을 확인해주세요.

 

$N$은 양의 정수입니다. $1 \le N \le 40$

아래, $N$ 개의 나라에 대한 정보가 한 줄에 하나씩 주어집니다.

$B_i$는 $i$번 나라의 여행 패키지에 참여한 경우의 만족도.

$C_i$는 $i$번 나라의 여행 패키지에 참여하지 않은 경우의 만족도.

$B_i$, $C_i$는 모두 $0$ 이상의 정수입니다. $0 \le B_i, C_i \le 100$.

 

$M$은 $0$ 이상의 정수입니다. $0 \le M \le \frac{N \times (N-1)}{2}$.

다음, $M$ 개의 조건에 대한 정보가 주어집니다.

$j$ 번째 조건은 $D_j$번과 $E_j$번 나라 모두 방문한다면,

$D_j$번 나라의 여행 패키지에 참여한다면, $E_j$번 나라의 여행 패키지에도 참여해야 한다는 것입니다.

$D_j, E_j$는 $0$ 이상 $N-1$ 이하의 정수입니다. $0 \le D_j < E_j \le N-1$.

$i \ne j$ 이면, $(D_i, E_i) \ne (D_j, E_j)$입니다.

출력

첫 번째 줄에 만족도의 최댓값을 출력해 주세요.

개행 문자를 출력해주세요.

풀이

힌트 1

$x$번 나라에 방문하지 않는다는 선택지가 없는 경우에 문제를 어떻게 풀 수 있을까요? 혹시 이 풀이를 $x$번 나라에 방문하지 않는다는 선택지가 있을 경우에도 확장할 수 있을까요?

힌트 2

$x$번 나라에 방문하지 않는다는 선택지가 없는 경우에는, $0$ 이상 $N-1$ 이하의 수를, 여행 패키지에 참가하지 않는 나라 $S$와 참가하는 나라 $T$로 나누는 문제가 됩니다. 여기서 $D_i \in T$ 이면 $E_i \in T$라는 조건이 있는 문제입니다.

이 문제에는 두 가지 풀이가 있습니다. 하나는 $N$에 대해 다항 시간 풀이고, 하나는 다항 시간이 아닌 풀이입니다. 각각을 힌트 3/풀이 1, 힌트 4/풀이 2라고 적겠습니다.

힌트 3

조건이 없을 경우의 답은 $\max(B_i, C_i)$ 전체의 합입니다. $i$가 $S$에 포함되면 답이 $\max(B_i, C_i) - B_i$만큼, $T$에 포함되면 답이 $\max(B_i, C_i)-C_i$ 만큼 깎이고, $D_j$가 $T$에 포함되었지만, $E_j$가 $S$에 포함된 경우에는, 답이 $\infty$만큼 바뀌는 문제가 되고, 여기서의 최댓값을 구하는 문제를 풀 수 있습니다.

이 방법을 안다면, 이 방법을 $x$번 나라에 방문하지 않는다는 선택지가 있는 경우에도 확장할 수 있습니다.

힌트 4

$N$ 개의 나라를, 처음 $\left\lfloor\frac{N}{2}\right\rfloor$ 개와, 끝 $\left\lceil\frac{N}{2}\right\rceil$ 개로 나눠봅시다. 여기서 각각의 경우를 모두 시도해 본 경우에, 둘을 합쳐주면 됩니다.

하지만 앞쪽 절반과 뒤쪽 절반 각각에 대해서 모두 다 해 보는 것도 $O(3^{N/2})$라는 시간이 들고, 충분히 빠르지 않을 수도 있습니다. 우리가 앞쪽 절반과 뒤쪽 절반을 합칠 때, 중요하게 생각해야 하는 정보는 무엇일까요? 그리고 이것을 빠르게 계산할 수 있을까요?

풀이 1

해당 문제는 방향 그래프의 최소 절단으로 해결할 수 있습니다. 시작 정점 $S$와 끝 정점 $T$를 만들고, 정점을 $N$ 개 추가로 만드는데, $S$에서 $i$로는, $i$가 $S$에 포함될 때의 비용, $i$에서 $T$로는 $i$가 $T$에 포함될 때의 비용, 그리고 $D_j$에서 $E_j$로는, $\infty$의 간선을 긋습니다.

최소 절단이 존재한다고 하고, $S$에서 $i$까지의 경로가 존재하면 $i$번 국가가 $S$에 포함된 것, 없으면 $T$에 포함된 것이라고 합시다. 이때 최소 절단은 문제의 조건을 만족하는 비용의 최솟값입니다. $D_j$에서 $E_j$로 간선을 긋는다는 의미는, $D_j$가 $S$에 포함되어 있을 때, 해당 $\infty$ 간선은 절단할 수 없기 때문에, $E_j$도 $S$에 포함되어야 하기 때문입니다.

 

해당 풀이를 확장해봅시다. 한 나라에 대해 정점을 두 종류 만듭시다. $i$와 $i'$을 만듭시다.

그리고

• $S$로부터 $i$와 $i'$ 모두가 도달 가능하면, 여행 패키지에 참여한다.
  • 이 때의 비용은 $\max(B_i, C_i) - C_i$.
• $S$로부터 $i$는 도달 가능한데, $i'$이 도달 불가능하면, 나라를 방문하지 않는다.
  • 이 때의 비용은 $\max(B_i, C_i)$.
• $S$로부터 $i$와 $i'$ 모두가 도달 불가능하면, 여행 패키지에 참여하지 않는다.
  • 이 때의 비용은 $\max(B_i, C_i) - B_i$.

와 같이 간선을 구성합시다. 이는 우리가 구상했던 이상적인 답인 $\max(B_i, C_i)$에서, 각각 비용이 해당 간선의 가중치만큼 깎인다는 것을 의미합니다.

$D_j'$에서 $E_j$까지 크기 무한대의 간선을 만든다는 뜻은, $S$에서 $D_j'$에 도달 가능하면 (즉, $D_j$번 나라의 여행 패키지에 참여하면), $E_j$에도 무조건 도달해야 한다. (즉, $E_j$번 나라의 여행 패키지에 참여하거나, 나라를 방문하지 않아야 한다.)라는 의미가 됩니다.

그래서, 해당 간선을 그어 준 이후에, 최소 절단을 구하고, $\max(B_i, C_i)$ 전체의 합에서 최소 절단을 빼준 것이 답이 됩니다.

총 시간은 정점이 $O(N)$, 간선인 $O(M)$ 개인 그래프의 flow입니다. 아래 코드는 Dinic Algorithm을 사용해서, $O(N^2M)$ 입니다.

 

코드: https://yukicoder.me/submissions/737871

풀이 2

앞쪽 절반과 뒤쪽 절반을 합칠 때, 사이에서 신경 써줘야 하는 조건인 "$x$번 나라의 여행 패키지에 참여하면, $y$번 나라의 여행 패키지에도 참여해야 한다. (혹은 $y$번 나라를 방문하지 않아야 한다)"에서 항상 $x<y$이기 때문에, $x$에 해당하는 나라는 앞쪽 절반, $y$에 해당하는 나라는 뒤쪽 절반 나라입니다.

결국, 앞쪽 절반은 "여행 패키지에 참여하는 나라"의 정보가 중요하고, 뒤쪽 절반은 "여행 패키지에 참여하거나, 방문하지 않는다"의 정보가 중요합니다.

 

여행 패키지에 참여하는 나라를 정하면, 나머지 나라에 대해서 여행 패키지에 참여하지 않을지 아니면 나라를 방문하지 않을지 여부는 greedy 하게 최댓값을 정할 수 있습니다. 특별한 조건이 없다면 나라를 방문하는 것이 이득입니다. 해당 조건의 판단은 $O(N)$ 정도에 가능합니다. (이 배열을 $f$라고 합시다.)

마찬가지로 뒤쪽 절반 나라에 대해서 "여행 패키지에 참여하거나 방문하지 않는 나라"를 정하면, "방문하지만, 여행 패키지에 참여하지 않는 나라"가 정해 지므로, 나머지 나라에 대해서도 역시 greedy 하게 최댓값을 정할 수 있습니다.

왜냐하면, 본 조건의 대우 명제가 "$y$번 나라(를 방문하지만, 해당하는) 여행 패키지에 참여하지 않으면, $x$번 나라의 여행 패키지에 참여해서는 안된다"이고, 특별한 조건이 없으면 여행 패키지에 참여하는 게 이득입니다. 해당 조건의 판단도 $O(N)$ 정도에 가능합니다. (이 배열을 $g$라고 합시다.)

 

이제 가능한 앞쪽 절반의 여행 패키지에 참여하는 집합 $S$에 대해서, 뒤쪽 절반에 여행 패키지에 참여하거나, 혹은 방문하지 않을 것이 강제되는 뒤쪽 절반에 해당하는 집합 $T$를 구할 수 있습니다. (이 역시, $O(N)$ 정도 시간에 구할 수 있습니다.) 여기서, 우리가 찾아야 할 것은 $f(S) + \max_{T \subseteq U} g(U)$입니다.

일반적으로 순회를 하면 최악의 경우 $U$가 공집합인 경우에, 모든 부분집합을 순회해야 하기 때문에 $h(T) = \max_{T \subseteq U} g(U)$를 구하는 데에 각 $T$당 $O(2^{N/2})$의 시간이 걸리지만, 전처리 $O(N2^{N/2})$로 $h(T)$를 가능한 모든 $T$에 대해 구할 수 있습니다.

 

어떤 집합 $S$에 대해서, 해당 $S$를 포함하는, $S$보다 크기가 1 큰 모든 집합의 $T$에 대해 $h(T)$를 구했다고 합시다. 이 경우에, $S$를 포함하는 모든 부분 집합은, $S$ 자체이거나, $S$보다 크기가 1 큰 집합 중 하나 이상을 포합 합니다. 그렇기 때문에, $h(S) = \max(g(S), \max_{i \not \in S} h(S \cup \{i\}))$로 구할 수 있습니다.

 

이 경우에, 총 시간 $O(N 2^{N/2})$에 문제를 해결할 수 있습니다.

 

코드: https://yukicoder.me/submissions/737453