PA 2016. Shuffle

문제에서 주어진 셔플 연산은 카드 덱을 뒤집는 연산과 동일합니다. 이 사실은 수학적 귀납법으로 증명 가능합니다.

$2$ 개의 카드에 대해서는 자명히 뒤집는 연산과 동일합니다.
$2^k$ 개의 카드에 대해서는, 덱을 절반으로 나눈 후 각각을 뒤집고 둘의 순서를 바꾸는 것이니, 이 역시 뒤집는 연산과 동일합니다.

카드 덱을 두번 뒤집는 건 아무것도 안하는 것과 동일하니, $t$ 가 홀수일 때 배열을 뒤집은 후 출력해 주면 됩니다.

ROI 2022 P5. Максимизация выигрыша

입력으로 주어진 문자열의 길이가 $19$ 이하일때만 문제를 해결할 수 있어도 됩니다. 만약 맨 앞 문자가 전체 문자열의 최댓값이 아닐 경우, 가장 가까운 최댓값을 맨 앞 문자로 옮깁니다. 이제 맨 앞 문자는 전체 문자열의 최댓값이니 이 문자를 출력하고 계속 반복하면 됩니다. 현재 문자열의 길이가 $n$ 일 때 문자를 옮기는 데 드는 비용은 $(n-1)y$, 옮겨서 얻을 수 있는 최소 이득은 $10^{n-2}$ 정도입니다. $y \le 10^{16}$ 인 입력 제한상 $n \geq 20$ 이면 이 연산이 무조건 유리합니다. 위와 같은 연산은 단순히 구현하면 $O(n^2)$ 정도인데, 우선 순위 큐 등 다양한 방법으로 $O(n \log n)$ 이나 $O(n)$ 정도로 최적화할 수 있습니다. 이 연산을 계속 하면 남는 문자열의 길이는 최대 $19$ 이고, 이 안에서 문제를 해결하면 됩니다.

문자열의 길이가 작을 때는 지수적 방법을 사용합니다. 문자열에서 위치를 옮기지 않을 문자들의 부분집합을 고정하고, 나머지 문자들은 모두 맨 앞으로 빼서 정렬한다고 했을 때의 결과를 계산합시다. 시뮬레이션 등으로, 옮기지 않는 문자가 고정되었을 때 얻게 되는 문자열, 그리고 그 때 필요한 교환 수를 계산할 수 있습니다. 이 정보들을 사용해 $2^n$ 개의 문자열들을 전부 비교해 보고 그 중 최댓값을 출력하면 됩니다.

문자열의 길이가 최대 $19$ 이기 때문에 모든 정보를 unsigned long long 에 담을 수 있습니다. 다만 채점 환경이 __int128 을 지원해서 그걸 쓰는게 훨씬 편해 보이긴 합니다. 사실 $19$ 가 아니라 $18$ 이라고 가정해도 AC가 뜨기 때문에 long long 만 써도 됩니다.

ROI 2022 P6. Экспедиция на Сириус

연산 자체가 꽤 복잡해 보이나 몇 가지 관찰을 통해 단순화할 수 있습니다.

연산을 몇 번을 하든 수의 최댓값에는 변화가 생기지 않습니다.
한번 같은 값을 가지게 된 두 숫자는 이후 다른 값을 가지게 되지 않습니다.
어떠한 두 숫자 $X < Y$ 사이에 다른 수가 없다면, $X, Y$ 사이의 "간격" 이 매 연산마다 $1$ 씩 줄어서 결국 $Y - X$ 번의 연산 이후에는 두 숫자가 같은 값을 가지게 됩니다.

각 수의 절대적인 값을 관리하기는 어렵지만, 숫자들을 정렬한 후, 수의 값을 최댓값을 기준으로 한 "간격" 의 합을 통해서 유도하면 관리가 상대적으로 쉬워집니다. $a_1, a_2, \ldots, a_n$ 을 정렬한 수열이라고 하면, $k$ 번의 연산이 적용된 이후 수열은 최댓값만 유지되고, 그 사이 원소들은 간격이 줄어들며 최댓값 방향으로 움직이는 형태를 띕니다. 그 때 줄어든 간격이 정확히 $k$ 이니, $b_i = b_{i+1} - \max(a_{i+1} - a_i - k, 0)$ 과 같은 점화식을 얻을 수 있습니다. 이 점화식을 그대로 사용하기만 해도, 각 쿼리당 $O(n)$ 시간에 문제를 해결할 수 있습니다. 이 풀이로 48점을 얻을 수 있습니다.

위 점화식에 기반하여 조금 더 생각하면 각 쿼리를 최적화하는 것도 가능합니다. 스위핑을 사용합니다. 쿼리를 $k$ 에 대한 증가순으로 처리합시다.

$a_{i+1} - a_i \le k$ 인 경우 두 수의 간격이 $0$ 이 됩니다. 고로 첫 번째 쿼리는 $n$ 에서 저러한 $i$ 의 개수를 빼서 출력하면 됩니다. $a_{i+1} - a_i$ 를 정렬한 후 Two pointers로 셀 수 있습니다.
두 번째 쿼리는 각 간격 이 답에 기여하는 정도를 합하면 됩니다. $i$ 번 수와 $i+1$ 번 수의 간격은 $k$ 번의 연산 후 $\min(a_{i+1} - a_i, k)$ 만큼 감소합니다. 고로 $i$ 개의 수에 대해서 이만큼 답이 증가했다고 생각할 수 있습니다. $\sum i \min(a_{i+1} - a_i, k)$ 의 합을 구하는 문제가 되는데, $a_{i+1} - a_i \le k$ 인 수들의 $i(a_{i+1} - a_i)$ 의 합, 그렇지 않은 수들의 $i$ 의 합을 구하면 됩니다. 1번 쿼리와 비슷하게 셀 수 있습니다.
세 번째 쿼리를 해결하기 위해 역배열을 둬서 $i$ 번 캐릭터가 정렬된 배열에서 어느 위치에 있는지를 확인합시다. 최댓값은 변하지 않으니, 문제는 어떠한 구간에 대해 $\sum \min(a_{i+1} - a_i, k)$ 를 합하고 이를 최댓값에서 빼면 해결됩니다. Fenwick tree로 일차 함수를 관리하는데, 만약 $a_{i+1} - a_i \le k$ 일 때는 일차 함수의 형태가 $0 x + (a_{i+1} - a_i)$ 이고, 그렇지 않은 경우 일차 함수의 형태가 $x$ 가 됩니다. $a_{i+1} - a_i = k$ 인 시점에 펜윅 트리 상에 일차 함수를 갱신하고, 쿼리가 주어질 때 구간의 일차 함수를 모두 합한 후 $x = k$ 를 대입하여 계산합니다.

시간 복잡도는 $O((n + q) \log n)$ 입니다.

ROI 2022 P7. Тяжелый груз

단순한 풀이는 지게차와 박스의 위치 쌍을 상태로 하여 문제에 나온 대로 모든 전이를 시도해 보고 최단 경로의 길이를 출력하는 것입니다. 이 풀이는 상태가 $O(n^2)$ 이기 때문에 직접 개선하기는 어렵습니다.

정점 $u$ 에서 박스를 들고 있는 지게차가 다른 상태로 바꿀 수 있는 방법은, 인접한 정점 $v$ 에 박스를 내려놓고, 다른 정점 $w$ 로 $v$ 를 거치지 않고 이동해서, $w$ 에서 박스를 주워가는 것입니다. 고로, 지게차와 박스가 같은 정점에 있는 상황만을 상태로 두면, 상태 전이는 다음과 같은 조건을 만족하는 정점 $w$ 에 대해서 가능합니다:

$u$ 와 $w$ 가 공통으로 인접한 정점 $v$ 가 존재하여, $v$ 를 지나지 않고 $u$ 에서 $w$ 로 이동하는 경로가 존재함

이렇게 하면 상태는 $n$ 개이지만 전이가 $O(n^2)$ 개일 수 있고 각 전이가 가능한지를 판단하는 것도 쉽지 않다는 문제가 있습니다.

전이 수를 최적화하기 위해서, 위 전이에서 $u$ 에서 $w$ 로 바로 이동하는 대신, 중간 정점 $v$ 에 대한 상태를 만들어주는 전략을 시도할 수 있습니다. 만약 $v$ 를 제거했을 때 그래프가 연결된다면, $u, w$ 가 뭐가 되든간에 $v$ 와 연결만 되어 있다면 상관이 없으니 이러한 전략이 올바르다고 할 수 있습니다. 문제는 $v$ 를 제거했을 때 그래프가 여러 연결 컴포넌트로 나뉘는 경우인데, 이 경우에는 $u, w$ 가 같은 연결 컴포넌트 안에 있어야 한다는 조건이 붙습니다.

이러한 조건을 분석하는 효과적인 방법은 이중 연결 요소 (Biconnected Component) 의 개념을 사용하는 것입니다. $v$를 제거했을 때 그래프가 여러 연결 컴포넌트로 나뉜다면 $v$ 는 절점 (cut vertex) 이며, $v$ 가 제거되었을 때 $u, w$ 가 같은 연결 컴포넌트 안에 있다는 것은 $(u, v), (w, v)$ 간선이 같은 이중 연결 요소에 속한다는 것과 같습니다. 절점 $v$ 에 대해서, $v$ 에 인접한 간선들은 최소 2개 이상의 이중 연결 요소에 속합니다. 상태를 정점 하나로 표현하지 않고, (정점, 정점에 인접한 간선의 이중연결요소 번호) 의 pair로 표현하면, 중간 정점 $v$ 에 대한 상태를 정보를 잃지 않고 표현할 수 있습니다.

이렇게 상태를 표현했을 경우, 박스와 지게차가 같이 있는 상태는 당연히 $n$ 개이고, 위와 같이 표현하는 상태의는 최대 $2m$ 개가 나오기 때문에 상태 수의 총 합은 $O(n + m)$ 입니다. 각 간선마다 상태 전이가 나오니 상태 전이의 수는 $O(m)$ 개입니다. 고로 그래프의 크기는 선형입니다.

잘 알려진 알고리즘을 사용하여 이중 연결 요소를 선형 시간에 계산하고, 상태 전이 그래프를 이중 연결 요소를 사용하여 각 전이당 $O(1)$ 이나 $O(\log n)$ 정도에 계산하고, 선형 크기의 그래프에서 BFS를 사용하면, 문제를 시간 제한 안에 해결할 수 있습니다.

ROI 2022 P8. Большие вызовы

$x$ 가 고정되었을 때 문제를 해결하는 것은 그리디하게 가능합니다. 우선순위 큐와 같은 간단한 자료구조만으로 각 $x$ 에 대해 문제를 $O((n + m) \log n)$ 에 해결할 수 있지만, 이 방법으로는 최적화하기 간단하지 않습니다.

대신 문제가 최대 매칭의 형태임을 관찰하고, 홀의 정리 (Hall's Theorem)을 사용하는 접근이 필요합니다. 다음과 같은 이분 매칭 문제를 생각합시다: 물통의 용량이 $a_i$ 개면, $a_i$ 개의 중복된 정점을 만들고, 수도관의 용량이 $c_i$ 개면, $c_i$ 개의 중복된 정점을 만든 후, 각 정점에 대응되는 물통/수도관이 연결되어 있다면 간선을 추가합니다. 이 그래프에서의 최대 매칭이 문제의 정답이 됩니다. 홀의 정리는 보통 완벽 매칭에 대해 논의되지만, 홀의 정리를 사용하여 최대 매칭 역시 구할 수 있습니다. 이분 그래프의 양 정점 집합이 $A, B$ 라면, $|A| - \max_{S \subseteq A}(|S| - |N(S)|)$ 가 최대 매칭의 크기가 되며, 홀의 정리의 statement만을 가지고도 이 사실을 어렵지 않게 증명할 수 있습니다. (위에서는 $a_i$ 를 중복된 정점으로 표현했지만, 이제부터는 편의상 정점은 $n+m$ 개이고 각 정점에 $a_i, c_i$ 의 용량 이 있다는 식으로 설명합니다. 네트워크 플로우의 용어랑 동일합니다.)

일단 모든 수도관의 타입이 $t_i = 1$ 이라고 가정합시다. $x$ 가 고정되어 있을 때, $l_x, r_x$ 를 $x$ 이하 / 이상 의 인덱스를 가지면서 $S$ 에 있는 $x$ 에 가장 가까운 원소라고 합시다. 모든 구간은 $x$ 를 지나기 때문에, 어떠한 구간이 $[l_x + 1, r_x - 1]$ 에 완전히 포함되어 있지 않은 이상 이 구간은 $N(S)$ 에 속합니다. $S$ 는 가능한 최대화되어야하기 때문에, $l_x$ 이하거나 $r_x$ 이상의 인덱스를 가진 원소들을 뽑지 않을 이유가 없고, 고로 $S$ 의 가능한 후보를 $O(n^2)$ 개로 한정시킬 수 있습니다. 구체적으로, $b[l, r]$ 을 $l \le l^\prime, r^\prime \le r$ 을 만족하는 수도관들의 $c_i$ 합이라고 하면, 최대 매칭은

$\sum a_i - \max(\sum a_i - b[1, n], \max_{l \le x, r \ge x}(\sum a_i - b[1, n] - \sum_{i = l}^{r} a_i + b[l, r]))$
$b[1, n] - \max_{l \le x, r \ge x}\max(0, b[l, r] - \sum_{i = l}^{r} a_i)$

$g_x = \max_{l \le x, r \ge x}( b[l, r] - \sum_{i = l}^{r} a_i)$ 라고 하면 답은 $b[1, n] - \max(0, g_x)$ 입니다. 고로 $g_x$ 를 빠르게 계산하면 됩니다. 이는 분할 정복을 사용하여 가능합니다. 라고 할 때, $dnc(l, r)$ 함수를 $l \le l^\prime \le x \le r^\prime \le r$ 을 만족하는 모든 $(l^\prime, r^\prime, x)$ 에 대해, $g_x = \max(g_x, b[l^\prime, r^\prime] - \sum_{i = l^\prime}^{r^\prime} a_i)$ 를 적용하는 함수라고 합시다. $dnc(l, m), dnc(m+1, r)$ 을 호출하면, 우리가 고려해야 할 구간은 모두 $l^\prime \le m \le m+1 \le r^\prime$ 을 만족합니다. 일반성을 잃지 않고 $x \geq m + 1$ 인 $x$ 에 대해서만 갱신한다고 합시다 (다른 쪽은 반대로 처리하면 됩니다). 이 경우 갱신해야 하는 함수들이 $[l, m] \times [x, r]$ 영역에 존재합니다. 고로 $[l, m] \times [x, x]$ 영역의 최댓값을 각각 구해준 후, 이의 suffix maximum을 계산하면 갱신해야 하는 함수 중 가장 큰 함수를 알 수 있습니다. 세그먼트 트리를 사용하여 필요한 최댓값들을 구해주면 이 분할 정복 과정은 $O((n+m)\log^2 n)$ 시간이 필요합니다.

수도관의 타입이 $t_i = 0$ 일 수 있는 경우를 생각해 봅시다. 이 경우에는 $l-1$ 이전 및 $r+1$ 이후에 있는 원소들을 선택하는 데 있어서 자유가 주어집니다. 자유가 주어진다고 특별히 $t_i = 1$인 원소들에 대해서 달라지는 것은 없지만, $t_i = 0$ 인 경우는 어떠한 연속된 물통 구간을 고르지 않음으로서 그 구간 안에 포함된 수도관들을 무시해 줄 수 있습니다.

$b^\prime[l, r]$ 을 $t_i = 0$ 인 원소들에 대한 수도관들의 $c_i$ 합이라고 합시다. 위에서 한 것과 동일한 이유로, $x \notin [l, r]$ 인 어떠한 구간 $[l, r]$ 의 물통을 $S$ 에 고르지 않으면, $b^\prime[l, r] - \sum_{i = l}^{r} a_i$ 만큼 $|S| - |N(S)|$ 값에서 손해를 보게 됩니다. 고로, $[l, r]$ 에서 보는 손해는 그대로 계산할 수 있고, $l-1$ 이전 및 $r+1$ 이후에 있는 원소들은 위 점을 감안하여 동적 계획법으로 계산할 수 있습니다. 구체적으로 $p_{l}$ 을 $[1, l]$ 구간에서 겹치지 않는 구간을 골랐을 때 보는 손해 합 최대, $s_r$ 을 $[r, n]$ 구간에 대해 동일하게 정의하면, 답은 $b[1, n] - \max_{l \le x, r \ge x} (\max(0, b[l, r] - \sum_{i= l}^{r} a_i) + p_{l-1} + s_{r+1})$ 과 같이 표현됩니다. $p, s$ 만 빠르게 구할 수 있으면 위의 분할 정복 풀이를 그대로 사용할 수 있는 형태이고, $p, s$ 는 세그먼트 트리를 활용한 DP로 계산할 수 있습니다.

2019/2020 GP of SPb. Removing Pairs

그리디 알고리즘으로 해결 가능합니다. 앞에서부터 처리하면서 두 문자가 같으면 무조건 매칭시키고 같지 않으면 긴 쪽의 두 문자를 무시해 줍니다. 알고리즘의 정당성은, 두 문자가 같을 때 한 쪽을 무시해주는 전략이 주는 이득이 없기에 성립합니다.

SEERC 2019. Absolute Game

벚꽃소녀 이환의 정수를 $b_1, b_2, \ldots, b_n$, 벚꽃소녀 지후의 정수를 $c_1, c_2, \ldots, c_n$ 이라고 두었을 때 $a_{i, j} = |b_i - c_j|$ 라는 2차원 배열을 만듭시다. 이환의 행동은 배열의 한 행을 지우는 것, 지후의 행동은 배열의 한 열을 지우는 것으로 볼 수 있습니다. 이 때 답은 $T = \max_{i \in [n]} \min_{j \in [n]} a_{i, j}$ 임을 증명할 수 있습니다:

벚꽃소녀 이환은 답이 나오는 $i$ 번 행을 무조건 살리면 되니 답은 $T$ 이상입니다.
정의상, $T$ 초과의 원소는 각 행에 $n-1$ 개 이하입니다. 벚꽃소녀 지후의 전략은, 서로 행과 열을 하나씩
지워가면서 $T$ 초과의 원소가 항상 $n − 1$ 개 이하로 유지되게 (고로 $n = 1$ 일 때 $0$개이게) 하는 것입니다. 만약 $T$ 초과의 원소가 정확히 $n − 1$개인 항이 없으면 아무 열이나 지워줍니다. 아니면, 그러한 행들을 모두
모아 교집합 상에 존재하는 원소를 아무거나 제거합니다. $(n − 1)^2 > n(n − 2)$ 라서 교집합이 비지 않아, 이것이 항상 가능합니다.

구하는 식의 특성상 $O(n \log n)$ 에 해결할 수도 있으나 여기서는 설명을 생략합니다.

Atcoder WTF 2022 Day2 A. Hat Puzzle

BOJ 30927 으로 업로드되었습니다.

폭탄의 개수를 $k$ 개라고 한다면, 각 벚꽃소녀의 폭탄 소지 여부로 가능한 경우의 수는 $\binom{n}{k}$ 개 입니다. 서술 편의상 폭탄 소지 여부를 01 로 이루어진 비트 문자열로 표현합니다.

먼저 Naive한 알고리즘을 생각해 봅시다. Naive 알고리즘에서는 가능한 모든 문자열 집합을 관리하고, 매 라운드가 끝난 이후 답의 후보를 반복적으로 줄입니다. 사실 이 후보 줄이기를 명확하게 하는 것이 쉽지 않은데, 이렇게 생각하면 구체화할 수 있습니다.

현재 시점에서 답으로 가능한 모든 문자열을 트라이(trie) 에 저장합니다. 즉, 맨 처음에 트라이에는 $\binom{n}{k}$ 개의 문자열이 있고 입력으로 주어진 문자열은 항상 그 중 하나입니다. $i$ 번 벚꽃소녀는 최종 문자열의 $i-1$ 개 글자를 알고 있습니다. 고로 트라이에서 답이 되는 문자열 방향으로 $i-1$ 번 내려간 노드를 알고 있지만, 답이 그 노드의 서브트리 중 어디에 있는지는 모릅니다.

$i$ 번 벚꽃소녀가 자신의 모자를 안다는 것은, 현재 노드의 자식이 정확히 한 개라는 것과 동일합니다. 고로, $n$ 명의 벚꽃소녀가 보고하는 답은, 답으로 가는 방향의 경로 상 각 노드의 자식 수와 동일합니다. 보고한 답을 토대로 트라이 상에서 자식 수가 보고된 결과와 맞지 않는 문자열들을 전부 지울 수 있고, 이를 어떤 벚꽃소녀도 탈출하지 않는 시점까지 반복하면 됩니다. 각 벚꽃소녀가 아는 정보의 정도는 다르지만, 결국 그 정도가 부분집합 꼴이기 때문에 현재 모든 벚꽃소녀의 정보를 전역으로 관리할 수 있습니다.

이제 지수 시간 알고리즘은 얻을 수가 있는데 이를 다항 시간으로 최적화해야 합니다. 놀랍게도 Naive 알고리즘에서 사용하는 자료구조를 살짝만 바꾸면 이를 해결할 수 있는데, 트라이 대신 격자 에 문자열을 저장하면 됩니다. 초기 $(0, 0)$ 에서 시작해서, 0 문자는 오른쪽, 1 문자는 위쪽으로 간다고 생각하면, 현재 시점에서 답으로 가능한 문자열을 격자 상의 경로로 볼 수 있습니다 (트라이 구조를 약간 포개서 생각했다고 봐도 됩니다).

$i$ 번 벚꽃소녀가 있는 위치는, $(0, 0)$ 에서 문자열을 따라 $i-1$ 번 움직인 위치입니다. 여기서 위 / 오른쪽으로 모두 갈 수 있다면 자식이 두 개인 것이고, 아니면 자식이 한 개인 것입니다. 보고한 답을 토대로, $(0, 0)$ 과의 거리가 같은데 자식 개수가 다르다면 해당 점을 지나는 문자열은 답의 후보에서 제거됩니다. 고로 답으로 남아 있는 문자열은 특정 점들을 지나지 않는 경로 와 일대일 대응됩니다. 이러한 방식으로 답이 지날 수 없는 점들을 반복적으로 지워주고, 더 이상 점이 지워지지 않을 때까지 반복하면 됩니다. 위 방식에서 지워지지 않아도, 경로가 지날 수 없는 점이라면 지워야 함을 유의하면 좋습니다 (예를 들어 $(1, 2), (2, 1)$ 이 지워졌다면 $(1, 1), (2, 2)$ 도 지워야 합니다). 이 때문에 단순 구현으로 점을 지울 수는 없고 DP를 사용해야 합니다.

라운드가 최대 $n^2$ 번 진행될 수 있기 때문에 단순히 생각하면 $O(n^4)$ 로 조금 느릴 수 있으나, 실제로 라운드가 최대 $n$ 번만 진행됨을 수학적 귀납법으로 보일 수 있어 시간 복잡도는 $O(n^3)$ 입니다.

Atcoder WTF 2022 Day2 C. Jewel Pairs

BOJ 30926 으로 업로드되었습니다.

기본적으로 Weighted General Matching이니까 다항 시간에 풀 수는 있는 문제이지만, General Matching을 최적화하는 방식으로 푸는 문제는 아닙니다.

문제에서 특이한 점은 간선마다 가중치가 부여되어 있는 것이 아니라 정점마다 가중치가 부여되어 있다는 것입니다. 어떠한 부분집합 $S \subseteq V$ 에 대해, $S$ 를 매칭으로 덮을 수 있다면 (완전 매칭이 존재하며 $S \subseteq T \subseteq V$ 인 부분집합 $T$ 가 존재하면) $S$ 를 독립 이라고 부릅시다. 우리는 가중치 합이 가장 큰 최대 독립 집합을 찾고 싶고, 이는 다음과 같이 가능합니다:

빈 집합 $S$ 로 시작한다.
모든 원소를 $b_i$ 가 큰 것부터 순서대로 처리한다. 만약 $S \cup {i}$ 가 독립이면 $i$ 를 넣는다.

이 알고리즘이 성립하는 이유는 독립 집합들이 Matroid를 이루기 때문입니다 (Matching Matroid). 몰라도 충분히 증명할 수 있지만 그냥 안다고 가정하겠습니다. 이제 $S$ 가 독립인지 여부를 판단하는 방법에 대해 고민해 봅시다.

$b_i \le k/ 2$ 가 만족될 시 $i$ 를 작다 고 하고 아닐 시 $i$ 를 크다 고 합시다. 작은 점과 큰 점들 간의 매칭에는 재미있는 성질들이 있습니다.

작은 점 간에는 색깔만 다르면 무조건 매칭이 됩니다.
큰 점 간에는 무조건 매칭이 되지 않습니다.
작은 점과 큰 점간의 매칭은 이분 그래프의 매칭과 같습니다.

원소들을 $b_i$ 가 큰 순서대로 처리하기 때문에 초기에는 $S$ 에 큰 점들만이 있습니다. $S$ 를 덮는 매칭은 무조건 작은 점과 큰 점을 이을 것이기 때문에, $S$ 에 큰 점들만이 있을 때 문제를 해결하는 것은 이분 매칭과 동치입니다. 이 문제는 이분 매칭으로 풀기에는 제한이 너무 크지만, $S$ 를 덮는 매칭의 존재를 찾는다는 점과 그래프 간선의 성질 때문의 홀의 정리 를 적용하기 적절합니다.

편의상 큰 점들에 대해서 $c_i = k - b_i$ 라고 정의합시다. 작은 점 $i$ 와 큰 점 $j$ 를 매칭하려면 $a_i \neq a_j$, $b_i \leq c_j$ 가 성립해야 합니다. 홀의 정리에 따라 매칭이 성립하지 않으려면 $|S| > |N(S)|$ 인 점이 필요합니다. $Low^B(a, x)$ 를 $a_i = a, b_i \le x$ 인 점 $i$ 의 수, $Low^C(a, x)$ 를 $a_i = a, c_i \le x$ 인 점 $i$ 의 수라고 하면, 모든 $(a, l, r)$ 에 대해서 다음 식이 $0$ 이하인지를 확인하는 것과 매칭이 존재함이 동치입니다:

$Low^C(a, r) - Low^C(a, l) + Low^C(\star, l) - Low^B(\star, r) + Low^B(a, r) - Low^B(a, l) \leq 0$

$a_i = \star$ 인 경우 모든 색이 다 허용된다는 뜻입니다. 각 $a$ 에 대해서 시도해야 할 $l$ 의 개수 및 $r$ 의 개수는 색이 $a$ 인 점 개수와 동일합니다. 또한 추가되는 큰 점의 크기가 계속 증가하기 때문에 고려해야 할 $r$ 도 계속 증가합니다. 고로 이 식은 $l$ 에 대한 prefix maximum 을 관리해서 (색이 $a$ 인 점이 들어오면 $a$ 에 대한 prefix maximum만 업데이트하는 식) 해결할 수 있습니다.

이제 $S$ 를 이루는 큰 점 이 무엇인지를 전부 결정했으니 작은 점 들을 결정해야 합니다. 만약에 $S$ 를 이루는 큰 점이 없다고 합시다. 이 경우 $S$ 를 이루는 최적의 작은 점 집합을 쉽게 결정할 수 있습니다. 매칭을 이루는 조건이 "색이 다르다" 뿐이기 때문에, 과반을 이루는 색이 없으면 웬만하면 완전 매칭이 존재하기 때문입니다. 정확히는:

만약 과반을 이루는 색이 없다면
- 전체 점이 홀수 개면 가장 가중치가 작은 점 빼고 전부 취함
- 전체 점이 짝수 개면 전부 취함
있다면
- 과반을 이루는 색에서 가장 가중치가 작은 점을, 색이 과반이 아닐때까지 반복해서 제거
- 이후 남은 점을 전부 취함 (점이 짝수 개임이 보장됨)

실제로는 $S$ 를 이루는 큰 점들에 의해 매칭될 작은 점들을 고르고, 그 후 그들 사이에서 위와 같은 방식으로 최적 집합을 구성해야 합니다. 작은 점들을 고정하는 방식으로 생각하면 지수 시간을 피할 수 없습니다.

대신, 작은 점들을 적당히 제거했다고 했을 때 과반을 이루는 색 $c$ 가 있다고 합시다. 우리가 이 $c$ 를 미리 안다고 하면, 큰 점들을 매칭한 작은 점을 고를 때 최대한 색 $c$ 를 많이 사용해서 지워주는 것이 좋습니다. 만약 색 $c$ 를 최대한으로 지운 결과 $f(c)$ 개의 점이 남았다고 합시다. 작은 점의 개수가 $A$, ($S$ 를 이루는) 큰 점의 개수가 $B$ 라고 하면, 색 $c$ 가 결과적으로 과반이 되었다는 것은 $2 f(c) > A - B$ 라는 것과 동일합니다. 즉, 색 $c$ 가 아닌 점들을 어떻게 지워도 상관이 없습니다 (그리고 $S$ 를 덮는 매칭이 존재하니 어떻게든 지울 수도 있을 것입니다). 결과적으로 해야 할 일은 $2f(c) - (A - B)$ 개의 색이 $c$ 인 점을 지워야 한다는 것입니다. 큰 점과의 매칭이 줄어들지 않는 선에서 가장 가중치가 작은 점들을 반복해서 지워주면 됩니다. $f(c)$ 를 모두 계산하는 것도 $O(n^2 \log n)$ 이고, 점을 지웠을 때 매칭이 줄어들지 않는지를 판별하는 것도 총합하면 $O(n^2 \log n)$ 입니다. 두 문제 다 작은 점과 큰 점을 매칭하는 문제로 볼 수 있는데, $b_i / c_i$ 순으로 점들을 정렬했을 때 큰 점보다 작은 점이 적은 prefix가 존재하는 것과 큰 점을 덮는 매칭이 없음이 동치입니다. 고로 점의 삽입 / 삭제와 함께 smallest prefix를 $O(\log n)$ 에 계산할 수 있는 자료 구조를 쓰면 두 문제를 $O(n \log n)$ 으로 최적화 할 수 있고 이는 세그먼트 트리를 사용하면 됩니다.

색 $c$ 가 결과적으로 과반이 되지 않았다면 가정이 깨지게 되어서 애초에 위와 같은 알고리즘을 사용하면 안 됩니다. 여기서 잠시 알아야 할 것은, $2f(c) > A - B$ 가 성립하는 $c$ 는 최대 하나만 존재합니다. 또 다른 $d$ 에 대해서도 $2f(d) > A - B$ 가 성립한다면, $d$ 를 우선해서 지웠기 때문에 $c$ 를 우선해서 지운것보다 많은 $c$ 가 남고 고로 $c, d$ 가 모두 과반이라는 결론이 성립하기 때문입니다. 위 식이 성립하는 $c$ 가 정확히 하나 존재했다면, 어떤 연산을 하더라도 $c$ 는 과반으로 남는다는 결론이 성립하고 고로 위 방법으로 문제를 해결하면 됩니다. 즉 현재 해결을 못 하는 케이스는 모든 $c$ 에 대해서 $2f(c) \le A - B$ 가 성립하는 케이스입니다.

$(A - B)$ 가 짝수라고 가정하고, 큰 수들을 모두 덮는 아무 매칭이나 찾아 봅시다. 매칭을 찾은 이후 과반인 색이 없다면 그것으로 끝납니다. 아닐 경우 어떤 색 $c$ 가 과반일 것입니다. $c$ 를 우선해서 지울 경우 $c$ 가 과반이 아니게 할 수 있습니다. 그러한 매칭과 현재 매칭의 XOR (symmetric difference) 를 취하면 alternating path들을 얻을 수 있습니다. alternating path들을 하나 취할 때마다 매칭에 덮인 수가 하나 제거되고 하나 추가될 것인데, 이 과정에서 $c$ 의 개수가 정확히 절반이 되는 지점이 존재합니다. 이 지점에서는 그 어떤 수도 과반이 될 수 없고, 고로 전체를 덮는 매칭이 존재합니다. 즉 모든 수를 취하면 됩니다.

$(A - B)$ 가 홀수라고 가정하면, $A$ 에서 수 하나를 제거해야 합니다. 무엇을 제거하든 $2f(c) \le A - B$ 여부를 바꾸진 않으니, 큰 수들을 덮는 매칭이 여전히 존재하는 가장 작은 가중치의 수를 아무거나 제거하면 됩니다. 위의 세그먼트 트리를 그대로 사용하면 됩니다. $O(n \log n)$ 에 전체 문제가 해결됩니다.

Atcoder WTF 2022 Day1 D. Welcome to Tokyo!

BOJ 30925 로 업로드되었습니다.

모든 $1 \le c \le M$ 에 대해서 각 파티의 비용이 $c$ 일 때 최대 이득을 계산하면 전체 문제를 Alien's Trick으로 풀 수 있습니다. 고로 이 변형된 문제를 해결하겠습니다.

갑작스럽지만, 다음 사실이 성립합니다.

각 파티의 비용이 $c$ 일 때 얻을 수 있는 최대 이득을 $P(c)$, $c+1$ 개 이상의 구간이 한 점을 포함하지 않는 부분집합의 최대 크기를 $Q(c)$ 라고 할 때, $P(c) + Q(c) = m$ 이다.

Atcoder 에디토리얼 은 LP relaxation로 위 두 문제를 모델링 한 후, LP Duality에 의해 objective function이 같음을 증명하고, 그 다음 LP에서 사용한 행렬이 totally unimodular 하여 relaxation을 하여도 답이 변하지 않는다 - 라는 식으로 증명합니다. 제가 아쉽게도 unimodularity에 대해 지식이 일천하여 이 증명을 설명할 수는 없고, 그냥 쉽게 이해할 수 있는 증명을 대신 소개하겠습니다.

Proof. 먼저 $P(c) + Q(c) \le m$ 을 증명한다. $m - Q(c)$ 개의 구간을 제거해서 모든 점이 최대 $c$ 개의 구간에 덮이게 하였다면, 이 경우 어떻게 파티를 열어도 절대 $0$ 초과의 이득을 볼 수 없다. 파티를 여는 비용이 $c$ 인데 비용을 메울 수가 없기 때문이다. 최적 파티에서 얻을 수 있는 이득은 ($m - Q(c)$ 개 구간에서 얻는 이득) + ($Q(c)$ 개 구간에서 얻는 이득) - (비용) 인데 위 논리에 의해 ($Q(c)$ 개 구간에서 얻는 이득) - (비용)이 $0$ 이하이니 $P(c) \le m - Q(c)$ 이다.

이제 $P(c) + Q(c) \geq m$ 을 증명한다. 최적의 방법으로 파티를 열어서 $P(c)$ 의 이득을 보았다고 하고, 이 때 파티를 연 위치를 $x_1, x_2, \ldots, x_k$ 라고 하자. 또한 이 방법이 가능한 방법 중 파티를 연 회수를 최소화한다고 하자. $x_1, x_2, \ldots, x_k$ 를 순서대로 돌며, 해당 위치를 포함하는 구간 수가 $d > c$ 개라면 이 중 아무 $d-c$ 개를 임의로 지우자. 최적해에 대해서

이 과정은 항상 $d > c$ 를 만족시킨다 (그렇지 않은 경우 파티를 안 여는 게 이득이다).
이 과정이 끝나면 $c$ 개 초과의 구간이 쌓여 있는 위치가 없다 (파티를 열어서 이득을 증가시킬 수 있다).
지운 구간의 수가 정확히 $P(c)$ 개이다.

고로 크기가 $m - P(c)$ 이상이며 $c+1$ 개 이상의 구간이 한 점을 포함하지 않는 부분집합이 존재하고, $Q(c) \geq m - P(c)$ 이다.

이제 문제는 모든 $c$ 에 대해 $Q(c)$ 를 계산하는 것입니다. 3분 그래프 리턴즈 와 같은 식으로 MCMF 네트워크를 만들면 $O(n^2 \log n)$ 에 문제를 해결할 수 있습니다. 네트워크는 대략 이런 식으로 생겼습니다.

$L_i \rightarrow (R_i + 1)$ 로 가중치 $-1$ 용량 $1$ 간선
$i \rightarrow i + 1$ 로 가중치 $0$ 용량 $\infty$ 간선

이후 $1$ 에서 $N + 1$ 로 유량을 하나씩 흘려주면 $-Q(1), -Q(2), -Q(3), \ldots, -Q(n)$ 을 모두 구해줄 수 있습니다.

이 문제를 $O(n \log n)$ 에 푸는 것은 이 풀이를 최적화하는 것으로 가능합니다. 유량을 하나 흘려주는 것은, 몇 개의 구간을 해집합에 추가하고 (정변) 또 원래 해집합에 있던 몇 개의 구간을 제거하는 (역변) 것으로 해석할 수 있습니다. 구간을 해집합에 추가할 때, 가능한 모든 구간 중 가장 끝점이 작은 구간을 추가하는 식으로 추가합시다. 이렇게 추가하면, Augmenting path를 찾을 때 해집합에 있던 구간을 제거하지 않아도 됩니다. 증명은, 끝점이 작은 구간만 뽑았다는 가정 하에서 가중치 $1$ 짜리 역변을 취하게 되면, 그 역변을 취하지 않아도 같은 비용의 답을 얻을 수 있게끔 항상 변환이 가능하다는 식으로 가능합니다.

문제는 구간을 추가하기만 하는 형태의 augmenting path를 효율적으로 구하는 것으로 볼 수 있습니다. 현재 $x$ 번 정점에 있다고 하면, 왼쪽 끝점이 $x$ 이상이면서 오른쪽 끝점을 최소화하는 구간을 세그먼트 트리로 구할 수 있습니다. 이 구간을 제거해 주고 구간의 오른쪽 끝점으로 움직이는데, 만약 오른쪽 끝점에서 $i \rightarrow i-1$ 로 가는 역변이 존재한다면 역변을 따라 최대한 왼쪽으로 다시 움직여 주고 반복합니다. 역변이 존재한다는 것은 해당 점을 덮는 구간이 $c$ 개 이하라는 것과 동일하기 때문에, Lazy propagation을 사용한 세그먼트 트리로 이 왼쪽 위치를 계산할 수 있습니다.

관련 있을 수도 있는 글들

2023.12.05 problem solving

댓글