홀의 결혼 정리 (Hall's marriage theorem)와 PS에서의 응용

홀의 결혼 정리(Hall's marriage theorem)는 여러 개의 집합이 주어졌을 때, 각 집합에서 서로 다른 수를 고를 수 있는 필요충분조건에 대한 정리입니다.

홀의 결혼 정리에 의하면, 집합들의 집합 \(S = \{A_1, A_2, \dots, A_k\}\)가 주어졌을 때 각 집합에서 서로 다른 수를 고를 수 있다는 것은 어떤 \(S\)의 부분집합 \(W\)을 선택하더라도 \(W\)의 원소들의 합집합의 크기가 \(|W|\) 이상이라는 것과 동일합니다.

 

CERC 2016. Bipartite Blanket

먼저 이분 그래프의 두 정점 집합에서 매칭이 존재하는 정점 부분집합을 따로 구해봅시다.

전부 \(O(2^n + 2^m)\)개의 경우가 있으므로 각각 홀의 결혼 정리를 만족하는지 검사한 뒤 가능한 정점의 부분집합을 모두 나열할 수 있습니다.

어떤 전체 정점의 부분집합에서 매칭이 존재하려면 \(A\)의 가능한 부분집합과 \(B\)의 가능한 부분집합의 합집합으로 나타낼 수 있어야 하고, 이렇게 나타낼 수 있다면 항상 가능한 매칭이 존재함을 보일 수 있습니다.

그러므로 가능한 \(A\)의 부분집합의 가중치 합과 가능한 \(B\)의 부분집합의 가중치 합을 모두 나열한 뒤, 이 두 배열에서 하나씩 골라 합이 \(t\)이상인 경우의 수를 구하면 됩니다.

두 배열을 정렬한 뒤 빠르게 경우의 수를 계산해 주면 답을 구할 수 있습니다.

POI 2008/2009. Ice Skates

\(a_i = \) 현재 발의 크기가 i인 사람인 수라고 정의합니다.

모든 사람에게 스케이트를 배정할 수 있을 조건은 홀의 결혼 정리에 의해 모든 \(l, r (1 \le l \le r \le n - d)\)에 대해 \(k * (r - l + d + 1) \ge (a_l + a_{l+1} + \dots + a_r)\)를 만족하는 것입니다. (연속적이지 않게 선택하는 경우 합집합의 크기를 늘이지 않고 추가로 선택하여 연속적으로 만들 수 있기 때문에 고려하지 않아도 됩니다.)

\(b_i = a_i - k\)라 하면 위 조건을 \(kd \ge (b_l + b_{l+1} + \dots + b_r)\)로 쓸 수 있고, \(kd\)는 \(l, r\)에 관계없이 일정하므로 \(kd\)가 \(b\)의 최대 구간 합 이상이라면 모든 사람에게 스케이트를 배정해 줄 수 있습니다.

\(b\)에서 업데이트 쿼리와 최대 구간 합 쿼리를 수행할 수 있으면 문제를 풀 수 있으므로 세그먼트 트리를 사용하여 해결할 수 있습니다. (KOI 2014 금광과 비슷한 방식으로 구간 합, 가장 왼쪽 수를 포함하는 구간 합 최댓값, 가장 오른쪽 수를 포함하는 구간 합 최댓값, 전체 구간 합 최댓값을 정의하여 관계식을 만들 수 있습니다.)

Petrozavodsk Winter 2019 Day 1. Dates

구간을 \(p_i\)가 큰 순서로 정렬하고, 구간을 추가하여도 매칭이 존재한다면 무조건 추가하는 방식으로 그리디하게 해결합니다. (이 전략의 증명은 matroid를 사용하여 간단하게 가능할 것 같습니다.)

추가된 구간들에 대하여 빠르게 매칭의 존재성을 판별하는 방법을 찾아야 합니다.

처음 순서 (\(l_i \le l_{i+1}, r_i \le r_{i+1}\)인 순서)에서 모든 구간의 부분집합을 고려할 필요 없이 연속된 구간만을 고려하여 홀의 결혼 정리를 적용해 주어도 상관없기 때문에, 세그먼트 트리를 사용하여 해결할 수 있습니다.

(어떤 구간의 부분집합에서 구간들이 서로 떨어져 있다면 각각의 떨어진 부분을 따로 고려하여도 되고, 붙어있는 부분에서 \(l_i \le l_{i+1}, r_i \le r_{i+1}\)이므로 내부의 선택하지 않은 구간을 선택하여도 합집합의 크기는 변하지 않습니다. 결국 연속한 구간만을 고려하여도 상관없습니다.)

홀의 결혼 정리의 조건을 식으로 나타내기 위해 다음과 같은 배열들을 정의합니다:

• \(S_i = a_1 + a_2 + \dots + a_i\)
• \(P_i = \) i번째 구간이 추가된 상태라면 \(1\), 아니면 \(0\)
• \(SP_i = P_1 + P_2 + \dots + P_i\)

모든 \(i, j (1 \le i \le j \le n)\)에 대해 \(S_{r_j} - SP_j - S_{l_i - 1} + SP_{i - 1} \ge 0\) 라면 추가된 구간에 대하여 매칭이 존재합니다.

위 식의 최솟값이 \(0\) 이상이면 되므로 최솟값을 구하기 위해 세그먼트 트리의 각 구간에서 다음과 같은 수를 정의합니다:

• \(mn = \) 구간에서 \(S_{r_i} - SP_i\)의 최솟값
• \(mx = \) 구간에서 \(S_{l_i - 1} - SP_{i - 1}\)의 최댓값
• \(answer = \) 구간에서 두 자식의 \(answer\)값과 (오른쪽 자식의 \(mn\)값 \(-\) 왼쪽 자식의 \(mx\)값) 중 최솟값 (리프 노드라면 \(mn - mx\)로 정의)

\(S\)에 관한 값은 구간의 추가에 영향을 받지 않으므로 처음에 업데이트를 해주고 시작합니다. 구간의 추가는 \(SP\) 배열의 구간에 \(1\)을 더하는 연산이므로, 세그먼트 트리의 연속된 구간의 \(mn\)와 \(mx\)에 \(1\)을 빼는 연산입니다. 그러므로 Lazy Propagation을 사용하여 해결할 수 있습니다.

 

각 구간을 그리디하게 추가하면서 루트 구간의 \(answer\) 값이 \(0\) 이상이라면 구간을 추가한 상태로 두고, 아니라면 다시 구간을 빼고 진행하면서 추가한 \(p_i\)의 값을 모두 더하면 답이 됩니다.