티스토리 뷰

공부/Problem solving

2025.01.05 problem solving

구사과 2025. 1. 6. 01:32

ARC 123 A. Arithmetic Sequence

$A_1 + A_3 = 2 \times A_2$ 가 되도록 각 수를 최소한으로 증가시키는 문제입니다. 위 부등식의 두 방향에 따라서 케이스를 나눠 처리하면 됩니다.

$A_1 + A_3 \le 2 A_2$ 면 $2A_2 - A_3 - A_1$ 만큼 $A_1$ (혹은 $A_3$) 을 증가시키면 됩니다.
$A_1 + A_3 > 2A_2$ 면 일단 $A_1 + A_3$ 이 짝수여야 합니다. 홀수일 경우 둘 중 아무거나 $1$ 만큼 증가시킵시다. 그리고 $A_2$ 를 $(A_1 + A_3) / 2$ 로 증가시키면 됩니다.

ARC 123 B. Increasing Triples

문제가 연산 을 도입하여 조금 난해하게 쓰여있습니다. 수열 $A$, $B$, $C$ 에서 $A_i < B_j < C_k$ 가 만족되게 원소를 각각 하나씩 고르고 지우는 걸 최대 몇 번 할 수 있는가로 해석하면 가장 자연스럽습니다. $A$, $B$, $C$ 의 초기 순서는 중요하지 않으니 세 수열을 모두 정렬하고 시작합시다.

만약에 답이 $T$ 라면, 최적해에서 고르게 될 $A$ 의 원소들은 $A_1, A_2, \ldots, A_T$ 가 됩니다. 그것보다 큰 원소를 고른다면 더 작은 원소로 바꿔줄 수 있기 때문입니다. 여기서 크게 두 가지 접근 방법이 있습니다:

같은 이유로, 고르게 될 $C$ 의 원소들은 $C_{N - T + 1}, C_{N - T + 2}, \ldots, C_N$ 가 됩니다. 답 $T$ 를 고정하면, 결국 $[A_i + 1, C_{i + N - T} - 1]$ 형태의 구간들이 있을 때 이 구간들에 $B$ 의 원소들을 하나씩 매칭할 수 있는가의 문제가 됩니다. 그리디하게 구간들을 끝점 증가 순서로 보면서 사용할 수 있는 가장 작은 $B_i$ 를 매칭하면 됩니다. 답 $T$ 를 이분탐색하면 $O(N \log N)$ 혹은 $O(N \log^2 N)$ 정도의 풀이가 나옵니다.
$A_1$ 에 매칭할 수 있는 가장 작은 $B$ 를 찾아 매칭하고, 그 $B$ 에 매칭할 수 있는 가장 작은 $C$ 를 찾아 매칭합니다. $A_2, A_3, \ldots$ 에 대해서도 이런 식으로, 수열 중 하나가 빌 때까지 반복합니다. 굳이 큰 $B$ 나 $C$ 를 고를 필요가 없기 때문에 정당성도 어렵지 않게 볼 수 있습니다. $B$ 와 $C$ 에서 매칭 안 된 첫 원소를 two pointer 처럼 관리하면 정렬 제외 $O(N)$ 에 가능합니다.

ARC 123 D. Inc, Dec - Decomposition

$C_i = A_i - B_i$ 로 대체하면, 각 조건은 $B_i \leq B_{i+1}, A_i - B_i \geq A_{i+1} - B_{i+1}$ 으로 변환됩니다. 이는 $B_i + \max(0, A_{i+1} - A_i) \leq B_{i + 1}$ 과 동일합니다. 이 조건을 만족하는 $B$ 중 $\sum |B_i| + \sum |B_i - A_i|$ 의 합을 최소화해야 합니다.

$S_i = \sum_{j < i} \max(0, A_{j+1} - A_j)$ 와 같이 씁시다. 이제 위 식을

$B_i + \max(0, A_{i+1} - A_i) \leq B_{i + 1}$
$B_i +\sum_{j \leq i} \max(0, A_{j+1} - A_j) \leq B_{i + 1} +\sum_{j < i} \max(0, A_{j+1} - A_j)$
$B_i - S_i \leq B_{i+1} - S_{i+1}$

과 같이 쓸 수 있습니다.

$X_i = B_i - S_i$ 라고 하면, 이 문제는 $\sum |X_i + S_i| + \sum |X_i + S_i - A_i|$ 의 합을 최소화하는 $X_1 \leq X_2 \leq \ldots \le X_N$ 을 찾는 것과 동일합니다. 이 문제는 여기까지만 정리해도 Slope Trick을 사용하여 해결할 수 있으나, 사실 한 가지 강한 관찰을 해서 더 단순한 문제로 정리할 수도 있습니다.

관찰은, $X_1 = X_2 = \ldots = X_N$ 인 최적해가 있다는 것입니다. 이유는 다음 조건이 성립하기 때문입니다:

$\min(-S_i, -S_i + A_i) \geq \min(-S_{i+1}, -S_{i+1} + A_{i+1})$
$\max(-S_i, -S_i + A_i) \geq \max(-S_{i+1}, -S_{i+1} + A_{i+1})$

증명은 $S_{i+1} = S_i + \max(0, A_{i+1} - A_i)$ 를 대입하고 전개하면 casework 없이 가능합니다

2차원 좌표 평면에 $(i, \min(-S_i, -S_i + A_i))$ 와 $(i, \max(-S_i, -S_i + A_i))$ 를 잇는 선분을 $N$ 개 그어봅시다. 그러면 우리가 구하는 $X$ 는 증가하는 형태의 체인으로 표현할 수 있고, 선분들은 (위 관찰에 의해) 감소하는 형태의 체인을 이루고, $X$ 가 선분 밖에 있으면 그 거리만큼 비용을 지불해야 합니다. 최적해의 $X$ 체인과 선분들이 처음으로 교차하는 지점을 기준으로 일직선을 이으면, 최적해가 그 일직선을 벗어났을 때 손해만 보게 됨을 알 수 있습니다.

고로 이제 문제는 $\sum |X + S_i| + \sum |X + S_i - A_i|$ 의 최솟값을 찾는 문제가 됩니다. 이분/삼분탐색으로 정답을 찾을 수도 있고, 함수 개형을 생각해보면 ${-S_1, -S_2, \ldots, -S_N, -S_1 + A_1, -S_2 + A_2, \ldots, -S_N + A_N}$ 의 중간값이 $X$ 의 최적 위치임도 알 수 있습니다. 후자를 사용하면 시간 복잡도는 $O(N)$ 입니다.

AGC 015 C. Nuske vs Phantom Thnook

먼저 전체 격자에서 흰색 연결 요소의 개수를 세어 봅시다. 이 문제는 DFS를 사용해서 해결하는 방법이 잘 알려져 있지만, 문제의 "흰색 연결 요소" 가 평면 그래프의 "흰색 면" 에 대응된다는 점을 활용하면, 단순 반복문으로도 해결할 수 있습니다. 평면 그래프를 그리는데, 하나의 흰색 연결 요소가 한 "흰색 면" 에 대응되도록 하고, 하나의 검은색 격자 가 한 "검은 면" 에 대응되도록 합시다. 이러한 평면 그래프를 구성하는 방법은 다음과 같습니다:

$(N + 1) \times (M + 1)$ 개의 정점을 각 격자의 꼭지점마다 만듭니다.
두 격자 중 하나 이상이 검은색 면이라면 두 면을 가르는 간선을 두 격자 사이로 만듭니다.
격자의 테두리에도 간선을 만듭니다.

이 그래프의 면의 개수는 검은색 격자의 개수와 흰색 연결 요소의 개수의 합과 동일합니다. 오일러 정리에 의해 연결된 평면 그래프에 대해 $V - E + F = 1$ 임이 성립합니다. 하지만 위와 같이 그래프를 구성할 경우 간선에 인접하지 않은 각 정점들이 독립된 컴포넌트를 이뤄서 연결 그래프가 아니게 됩니다. 이는, 차수가 $0$ 인 정점을 무시해주는 식으로 해결할 수 있습니다. 이렇게 되면 정점, 간선, 그리고 검은색 격자 수를 단순 반복문으로 세어주면 문제를 해결할 수 있습니다.

직사각형 쿼리가 추가되어도 똑같습니다. 직사각형 영역 내 정점, 간선, 그리고 검은색 격자 수를 2차원 부분합으로 세어주면 됩니다.

전체 시간 복잡도는 $O(NM+Q)$ 입니다.

PA 2024. Grupa permutacji

먼저 $O(n^2k)$ 풀이를 설명합니다. 기댓값의 선형성을 사용하면, 위치 쌍 $1 \le i < j \le N$ 에 대해서, $p_i > p_j$ 가 될 확률을 계산한 후 이를 모두 합쳐주는 것으로 문제를 변환할 수 있습니다. 초기에 위치 $(i, j)$ 에는 값 $(i, j)$ 가 적혀 있지만, $1 \le x \le k$ 번 순열을 적용하면 이 값을 $(p_{x, i}, p_{x, j})$ 로 바꿀 수 있습니다. 이렇게 값 $(i, j)$ 가 $(p_{x, i}, p_{x, j})$ 로 변환가능하다면 두 정점 사이에 간선을 이어줍시다. 이 연결 컴포넌트 안에 있는 모든 값 쌍은 연산을 반복 적용해서 얻을 수 있고 (정의상 자명), 또한 모든 값 쌍은 순열에서 등장할 확률이 동일합니다 ($k$ 에 대한 귀납법). 이제 문제는 그래프 문제가 됩니다. 모든 $1 \le x \le k$ 에 대해서 $(i, j)$ 와 $(p_{x, i}, p_{x, j})$ 간에 간선을 이어줍시다. 문제의 정답은, $1 \le i < j \le N$ 에서 도달할 수 있는 $(a, b) (a > b)$ 꼴의 정점 수를 컴포넌트 크기로 나눈 것의 합이 됩니다.

만약에 순열들이 충분히 랜덤하다면, 한 순열만 봐도 이미 많은 간선을 얻을 수 있어서 필요 없는 순열들이 많을 것이라고 생각할 수 있습니다. 실제로는, 정보량이 적은 (예를 들어 $A[i] = i$ 인데 특정 $j \le n/2$ 에 대해서만 $A[j] = j+n/2, A[j+n/2] = j$ 인 경우) 순열들을 여러개 줄 수 있어서 항상 봐야만 하는 경우들이 존재합니다.

이 경우를 해결하기 위해 랜덤 알고리즘을 사용합시다. 한 번의 반복에서는, 각 순열을 $1/2$ 확률로 고른 후 이들을 모두 합성하고, $O(n^2)$ 시간에 이 순열을 적용해서 얻을 수 있는 간선들을 모두 추가해 줍니다. 직관적으로는, 이렇게 얻은 순열들은 충분히 랜덤하고 정보량도 크니, 모든 순열이 랜덤한 케이스랑 크게 다르지 않다고 생각할 수 있습니다.

이 연산을 $O(\log n)$ 번 반복하면, 매우 높은 확률로 올바른 연결 컴포넌트 집합을 얻을 수 있습니다. 이를 증명하기 위해서는, 매 연산에서 특정 연결 컴포넌트가 $1/2$ 의 확률로 다른 연결 컴포넌트랑 합쳐지며, 이 과정에서 해당 연결 컴포넌트의 크기가 최소 $2$배 된다는 것을 증명해야 합니다. (small-to-large 논증이 아니고 모든 컴포넌트가 2배 커져야 합니다). 이 사실을 증명하면 각 컴포넌트가 $O(\log n)$ 번 정도면 $n^2$ 의 크기에 도달해서 더 이상 합쳐질 수 없는 상태에 도달하기 때문에 풀이의 정당성이 따라옵니다. 해당 증명은 귀납법을 사용하며 여기서는 생략합니다.

전체 시간 복잡도는 $O(n(n+k) \log n)$ 입니다. (반복은 50번 정도만 해도 만점이 나옵니다.)

PA 2020. Mieszanie kolorów

세 종류의 색깔에 대해서 해당 색깔이 $i$ 번 페인트통에 존재하는지 여부를 배열로 관리하면 문제를 해결할 수 있습니다. 각 쿼리가 들어왔을 때, 단순하게 반복문을 돌려서 이 배열을 관리하면 $O(NQ)$ 시간이 들지만, 변홧값 배열을 사용하면 이를 $O(N+Q)$ 로 최적화 할 수 있습니다.

PA 2020. Zabawki

문자열 $S$ 가 주어졌을 때, 홀수 인덱스에 있는 문자들만 모아서 문자열 $S_0$ 을 만들고, 짝수 인덱스에 있는 문자들만 모아서 문자열 $S_1$ 을 만듭시다. 길이 3의 부분문자열을 뒤집는 것은, $S_0$ 이나 $S_1$ 에서 인접한 두 문자를 교환하는 것과 동일한 연산입니다. 또한, 어떤 홀수 길이의 부분문자열을 뒤집어도 $S_0, S_1$ 간에 문자들이 섞이지 않습니다.

인접한 두 문자를 교환할 수 있으면, 문자열을 정렬할 수 있습니다. 역으로, 정렬된 문자열에서 원하는 문자열을 얻을 수도 있습니다. 즉, $S = (S_0, S_1), T = (T_0, T_1)$ 과 같이 분해했을 때, $S_0$ 과 $T_0$ 을 정렬한 결과가 같다면, $S_0$ 에서 인접한 문자들만 교환해서 $T_0$ 을 얻을 수 있습니다. 반대로, 정렬한 결과가 다르다면, $S_0$ 의 문자들을 어떻게 재배열해도 $T_0$ 을 얻을 수 없습니다.

결론적으로, $S_0, T_0$ 을 정렬한 결과가 같고 $S_1, T_1$ 을 정렬한 결과가 같으면 답이 YES 가 됩니다. 조건을 확인하는 것은 그냥 정렬해 봐도 되고 각 문자의 등장 횟수를 세어 비교해도 됩니다.

PA 2020. Elektrownie i fabryki

인덱스 $i_1, i_2, i_3, \ldots, i_k$ 에 대해서 $i - (i+1)$ 간의 전선을 설치하지 않았을 때 이 해가 올바른지의 조건을 확인합시다. 설치하지 않은 두 인덱스 사이 구간에는 전기를 전부 공유할 수 있으니, 그 안에서 $a_i$ 의 합이 $0$ 이상이면 조건을 만족한다고 볼 수 있습니다. 부분합 배열 $S_i =a_1 + a_2 + \ldots + a_i$ 를 만들면:

$[1, i_1]$ 구간의 전기량 합 0 이상: $S_{i_1} \geq S_0$
$[i_1+1, i_2]$ 구간의 전기량 합 0 이상: $S_{i_2} \geq S_{i_1}$
$\ldots$
$[i_k + 1, n]$ 구간의 전기량 합 0 이상: $S_n \geq S_{i_k}$

전선은 최대한 적게 설치하는 것이 경제적이니, 결국 문제는 $S_0 \leq S_{i_1} \leq S_{i_2} \leq \ldots \leq S_{i_k} \leq S_n$ 을 만족하는 최대 길이 부분수열을 찾는 문제가 됩니다. $S_0 \le S_i \le S_n$ 범위에 있는 $i$ 만 사용해서, 최장 증가 부분수열 (LIS) 를 구하면 이를 찾을 수 있습니다. 시간 복잡도는 $O(n \log n)$ 입니다.

BOJ 25662. Flower's Land

1번 정점이 루트인 경우 문제를 해결하는 방법을 생각해 봅시다. 일반적인 방법은 검은 돌 트릭 을 적용해서 $O(nk)$ 시간에 작동하는 DP를 구현하는 것인데, 이를 모든 루트에 대해서 그대로 적용하면, 양방향 트리 DP를 사용하더라도 시간 초과가 날 것 같습니다.

사실, 트리의 Euler tour에다가 DP를 하는 식으로 더 간단한 방식으로 문제를 해결할 수 있습니다. 1번 정점을 포함하는 연결된 서브트리를 고르는 것은, 1번 정점을 루트로 한 트리에서 몇 개의 서로소인 서브트리를 제거하는 식으로 생각할 수 있습니다. Euler tour를 생각해보면 서로소인 서브트리는 서로소인 구간으로 표현할 수 있습니다. 고로 문제는 겹치지 않는 구간을 골라서 $n - k$ 개의 원소들을 덮고, 덮이지 않은 원소들의 크기 합 최대를 구하는 문제가 됩니다. 이렇게 하면 점화식은:

$DP_{i, j} = \max(DP_{i + sz_i, j}, DP_{i + 1, j - 1} + A[i])$

와 같이 표현됩니다. (편의상 노드 번호가 Euler tour에 맞게 매겨져 있다고 합시다. $sz_i$ 는 $i$ 의 서브트리 크기입니다.)

이제 각 노드 $v$ 에 대해서 문제를 해결해야 합니다. 위 풀이를 조금 응용하면, $1$ 번 정점과 $v$ 번 정점을 모두 포함한 서브트리의 최대 합을 구할 수 있습니다. 위 DP는 결국 $(0, 0) \rightarrow (n, k)$ 로 가는 최대 가중치 경로를 구하는 문제이고, 우리가 구하고자 하는 건 $(v, j) \rightarrow (v + 1, j + 1)$ 이라는 간선을 지나는 경로 중 가중치 최대인데, $L_{i, j}, R_{i, j}$ 를 각각 $(0, 0) \rightarrow (i, j), (i, j) \rightarrow (n, k)$ 로 가는 최대 가중치 경로의 길이라고 정의하고 구하면 특정 간선을 무조건 지나는 최장 경로 역시 구할 수 있습니다. 이 부분의 시간 복잡도는 $O(nk)$ 입니다.

실제로는, $1$ 번 정점을 포함하지 않는 서브트리가 최적일 수도 있다는 것이 문제입니다. 이는 늘 그렇듯 Centroid decomposition을 써서 centroid를 포함하는 최대 서브트리를 구하고, 그 안의 경우는 재귀적으로 해결하면 됩니다. 이렇게 하면 복잡도가 $O(nk \log n)$ 이라서 너무 커 보이지만, 실제로는 크기 $k$ 미만의 서브트리를 볼 필요가 없어서 $O(nk \log(n / k))$ 가 되고 통과하기 충분합니다.

사실 이 문제는 양방향 트리 DP를 사용해서 풀어도 검은 돌 트릭처럼 "불필요한 상태 전이를 전혀 하지 않으면" $O(nk)$ 의 복잡도를 얻을 수 있습니다. 부모 상태에서 내려오는 테이블의 크기가 항상 $O(k)$ 일 수 있어서 그렇지 않다고 생각할 수 있겠지만, 부모 테이블에서 $[k - sz_v, k]$ 의 구간만 신경쓰는 식으로 처리하면 기존 검은 돌 트릭과 동일한 이유로 $O(nk)$ 의 시간 복잡도가 나옵니다.

AGC 045 E. Fragile Balls

모든 군인들이 $C_i = 1, A_i \neq B_i$ 를 만족하면, 이동이 가능한지 여부만 판별하면 됩니다. 가능하면 답이 $M$ 이고, 가능하지 않으면 답이 $-1$ 이기 때문입니다. 일단 이 특수 케이스를 먼저 생각해 봅시다.

각 군인들을 $A_i \rightarrow B_i$ 로 가는 방향 간선으로 생각하고, 그래프를 SCC로 분해합시다. 만약에 어떠한 SCC가 길이 2 이상의 simple cycle이고, 다른 SCC와 전혀 연결되어 있지 않다면, 답이 존재하지 않습니다. 다시 말해, 무방향 그래프로 봤을 때 사이클 모양의 컴포넌트면 답이 존재하지 않습니다. (이를 나쁜 사이클 이라고 합시다.) 이 사이클에서 처음으로 군인을 이동시키는 시점을 생각해 보면, 사이클 밖에 있는 다른 군인이 해당 정점에 들어와야만 정점을 나갈 수가 있는데, $C_i = 1$이기 때문에 어떤 군인이 해당 정점에 들어오면 다시 나갈 수가 없습니다.

그렇지 않다면 항상 모든 군인들을 이동시킬 수 있습니다. indegree가 없는 SCC를 아무거나 고릅시다. 문제 조건상 모든 정점의 indegree가 1 이상이고, 나쁜 사이클이 없기 때문에, 이 SCC에는 outdegree가 2 이상인 정점이 존재해야만 합니다. 이 정점을 $v$ 라고 합시다. $v$ 를 지나는 방향 사이클을 ${v, v_1, v_2, \ldots, v}$ 라고 하면 (SCC니까 무조건 존재), $v \rightarrow v_1$ 에 대응되는 군인을 옮겨주고, $v_1$ 에서 사이클에 속하지 않은 군인들을 모두 해당 방향으로 풀어주고 ($v_1$ 에 추가 군인이 있기 때문에 가능), $v_1 \rightarrow v_2$ 에 대응되는 군인을 옮겨주고... 를 반복할 수 있습니다. 이 과정이 끝나면 해당 방향 사이클에서 출발하는 군인들은 모두 제자리에 도착하며, 또한 사이클에서 거리 $1$ 인 정점들은 모두 새로운 군인을 받게 되어서 기존 군인들을 옮겨줄 수 있습니다. 이 과정을 반복하면 $v$ 에서 도달 가능한 모든 정점들을 처리할 수 있고, 이를 모든 indegree가 없는 SCC에 대해서 반복하면 됩니다.

결론은, 나쁜 사이클이 없는 경우에는 항상 $M$ 번의 이동으로 목적을 달성할 수 있습니다. 이건 $C_i \geq 1$ 로 조건이 바뀌어도 변하지 않으며, $A_i = B_i$ 인 군인이 추가되어도 ($M$ 에서 무시해야 한다는 것을 제외하면 변하지 않습니다.) 결정 문제 뿐만 아니라 최소화 문제까지 해결된 것입니다.

이제, 나쁜 사이클이 $X \geq 1$ 개 있는 경우를 생각해 봅시다. 잠시 $A_i \neq B_i$ 가 항상 성립한다고 가정합시다. 처음에 한 번이라도 이동을 하기 위해서는, 그래프에 나쁜 사이클이 아닌 무방향 연결 컴포넌트가 존재해야 하며, 이 컴포넌트에 $C_e \geq 2$ 인 간선이 존재해야 합니다. $C_e \geq 2$ 인 간선이 존재할 경우, 대응되는 군인은 목적지에 들어가기 전 $C_e - 1$ 번 추가적인 이동을 할 수 있고, 각 이동마다 사이클 하나를 풀어줄 수 있습니다. $X$ 개의 사이클을 전부 풀어줘야 하기 때문에, $\sum (C_i - 1) \geq X$ 를 만족해야 합니다. 이것이 만족되면 항상 모든 군인을 $M + X$ 번에 이동시킬 수 있습니다: 나쁜 사이클이 아닌 경우에 대해서 모두 군인들을 제자리로 이동시키고, 그 과정에서 추가 이동 횟수가 남은 군인이 발견되면 목적지에 가기 전에 나쁜 사이클로 해당 군인을 보냅니다. 그 이후 나쁜 사이클을 풀어주고, 그 안에서 또 추가 이동 횟수가 남은 군인이 발견되면 풀어주고... 나쁜 사이클을 방문할 때, 추가 이동 횟수가 남은 군인이 있는 사이클을 우선적으로 방문하기만 하면, 항상 모든 $\sum (C_i - 1)$ 개의 추가 이동을 의미있는 방식으로 사용할 수 있습니다.

이제 $A_i = B_i$ 인 간선까지 추가해 봅시다. 해당 간선을 무시했을 때 첫 이동이 가능하며 $\sum (C_i - 1) \geq X$ 가 만족한다면, 어차피 그것보다 잘 할수는 없으니 그냥 처음처럼 해당 간선을 무시해 주면 됩니다. 결국 $\sum (C_i - 1) < X$ 일 때 $A_i = B_i$ 인 군인까지 사용해서 첫 이동을 하고, 최대한 사이클을 풀어주고 싶은 경우가 문제입니다. $A_i = B_i$ 인 간선은 정의상 나쁜 사이클에 있을 순 없고, 무방향 컴포넌트의 크기가 1이거나 아니면 나쁜 사이클이 아닌 큰 무방향 컴포넌트에 있습니다. 나쁜 사이클이 아닌 무방향 컴포넌트에 있으면 그냥 앞의 경우와 차이가 없습니다. 문제는 무방향 컴포넌트의 크기가 1이고, 그 간선 말고 다른 간선이 없는 경우입니다. 이 경우에는 이 간선을 사용하려면 다른 군인이 정점을 방문해야 하니까, 결국 $C_i - 1$ 번의 이동을 위해서 $X$ 를 하나 증가시키는 꼴이 됩니다.

고로, $Y$를 "정점 및 간선이 단 하나밖에 없는 컴포넌트에 속하는 군인 중, 이동에 사용하기로 약속한 군인의 수" 로 정의합시다. 이 군인들을 사용하기 위해서는 나쁜 사이클처럼 누군가가 자신들을 방문해야 하니, $\sum (C_i - 1) \geq X + Y$ 가 성립해야 합니다. 답을 판별하기 위해서는, $C_i$ 가 큰 $Y$-군인들순서대로 반복해서 넣어보고 답이 되는지 확인하면 됩니다.

이제 최소화 문제를 생각해 봅시다. $A_i \neq B_i$ 인 군인 수 + $X$ 는 무조건 지불해야 하는 필수 비용입니다. 또한 $X > 0$ 인 경우 첫 시작을 해야 하니 $C_e \geq 2$ 인 간선이 나쁜 사이클이 아닌 곳에 있어야 합니다 (이 간선이 $A_e = B_e$ 인지 아닌지의 여부가 중요합니다). 마지막으로, $\sum (C_i - 1) \geq X$ 를 최소 비용으로 만족해야지 이동이 가능합니다.

$A_i = B_i$ 인 군인 중 간선이 두개 이상인 무방향 컴포넌트에 있는 군인들은, 꼭 옮길 필요가 없으니, $1$ 의 비용으로 $C_i - 1$ 의 이득을 줍니다.
$A_i = B_i$ 인 군인 중 간선이 1개인 무방향 컴포넌트에 있는 군인들은, $2$의 비용 (본인이 이동 + 나쁜 사이클 하나 증가) 으로 $C_i - 2$ 의 이득을 줍니다 (조건 상 $Y$ 가 증가함)

이를 감안해서 이득의 합을 $X$ 이상으로 만드는 최소 비용을 더해주면 됩니다. 이득 감소순으로 정렬한 후, $2$ 의 비용을 주는 군인 수를 고정하고 two-pointers로 답을 찾아주면 됩니다. 시간 복잡도는 $O(m \log m)$ 입니다.

ABC 218 E. Destruction

제거한 간선의 가중치 합을 최대화하는 대신 남겨둔 간선의 가중치 합을 최소화하는 문제를 해결합시다. 모든 $\sum C_i$ 의 합을 구한 후 최솟값을 제거하면, 원래 문제와 똑같습니다.

만약 $C_i \geq 0$ 인 입력만 주어진다면, 이 문제는 정확히 최소 스패닝 트리 문제입니다. 이 문제는 Kruskal's algorithm을 사용하여 해결할 수 있습니다.

여기서는 $C_i < 0$ 인 간선들이 주어지는 것이 차이점인데, $C_i < 0$ 인 간선들을 사용하면 그래프의 연결에 도움이 되고 가중치 합도 줄일 수 있으니 무조건 이 간선들은 남겨 두는 게 좋습니다. Kruskal's algorithm에 사용하는 union-find에서 $C_i < 0$ 인 간선들을 모두 추가해놓고, 남은 간선들은 일반적인 Kruskal's algorithm과 동일하게 연결에 도움이 될 때만 추가하면 됩니다.

ABC 218 F. Blocked Roads

단순한 접근은 모든 간선을 한 번씩 제거해 본 후 BFS로 최단 경로를 계산해 보는 것입니다. BFS가 $O(N^2)$ 의 시간을 사용하고, 간선의 개수가 $M$ 개이니, 이 접근은 $O(MN^2) = O(N^4)$ 의 시간이 소모되어 제한 안에 문제를 해결할 수 없습니다.

모든 간선이 있는 상태에서 BFS로 $1$ 번 정점에서 $N$ 번 정점으로 가는 최단 경로를 하나 계산해 둡시다. 단순히 거리만 계산하는 것이 아니라 경로를 역추적해서 계산합니다. 이 경로에는 최대 $N-1$ 개의 간선이 있습니다. (경로가 없으면 예외처리 해 둡시다.)

만약 $i$ 번 간선이 위 경로에 속하지 않는다면 답은 바뀌지 않습니다. 최단 경로가 그대로 살아 있기 때문입니다. 경로에 속한다면, BFS로 최단 경로를 다시 계산해 줍시다. 이렇게 하면 BFS를 $M$ 번이 아니라 최대 $N$ 번 돌리기 때문에, 시간 복잡도가 $O(N^3)$ 으로 줄어들고 제한 안에 문제를 해결할 수 있습니다.

ABC 218 H. Red And Blue Lamps

일반성을 잃지 않고 $K \leq N - K$ 이라고 가정합시다 (아니면 색을 바꾸면 됩니다.)

핵심 아이디어는 $K$ 개의 빨간 정점을 인접하지 않게 고르는 최적해가 항상 존재한다는 것입니다. 이 사실에 대한 증명은 아래에 서술합니다. 빨간 정점끼리 인접하지 않는다면, 결국 최종적으로 남는 간선은 정확히 하나의 빨간 정점을 포함하는 정점입니다. 그래서 각 정점을 빨간 정점으로 바꿨을 때 얻는 이득이 독립적으로 분리되고, 최종적으로 길이 $N$ 의 배열에서 $K$ 개의 인접하지 않는 점을 골라서 점의 가중치 합을 최대화하라는 문제로 환원됩니다.

이 문제는 APIO 2007 백업 이라는 문제와 동일합니다. 그리디하게 Augmenting path를 관리하는 풀이도 잘 알려져 있고, 위 풀이에서 Convexity가 따라온다는 점을 사용하여 Alien's trick을 사용하는 풀이도 잘 알려져 있습니다. 고로 전체 문제가 $O(N \log N)$ 에 해결됩니다.

이제 $K$ 개의 빨간 정점을 인접하지 않게 고르는 최적해가 항상 존재함을 증명합니다. 먼저, $K$ 개의 빨간 정점을 인접하지 않게 고르는 최적해가 주어졌을 때 이를 $K^\prime (\leq K)$ 개의 빨간 정점을 인접하지 않게 고르는 최적해로 변환합니다. 이 최적해에서 $k \geq 2$ 개의 빨간 점이 연속해서 등장하는 구간을 찾아봅시다. 만약에 $k > 2$ 라면, 연속 구간에서 두 번째로 등장하는 빨간 점을 지워주면 가중치를 줄이지 않으면서 연속 구간의 길이가 $k-2$ 로 줄어듭니다. 이를 반복하면 빨간 점은 $1$ 개 혹은 $2$ 개씩 인접하게 됩니다. 만약 빨간 점이 $2$ 개씩 인접한다고 하면, 이중 하나를 뒤집고, 원래 남기던 간선을 유지하면서 그쪽 방향의 점들을 계속 뒤집어서 인접한 쌍을 지워줍니다. 예를 들어

ooxoxoxx -> oxoxoxox (뒤집는 방향의 끝에서 인접한 파랑 정점 쌍 발견)
ooxoxoo -> oxoxoxo (뒤집는 방향의 끝에서 인접한 빨간 정점 쌍 발견)

이와 같이 하면 이득을 취하는 간선 집합을 지우지 않으면서 연속 구간의 개수를 줄일 수 있습니다. 이 연산은 $K \leq N/2$ 이기 때문에 무조건 가능합니다. (오른쪽이나 왼쪽 중 하나는 무조건 뒤집을 수 있습니다.)

마지막으로 $K^\prime$ 개의 빨간 정점을 인접하지 않게 고르는 최적해를 $K$ 개의 빨간 정점을 인접하지 않게 고르는 최적해로 변환해야 합니다. 결국 인접한 정점을 $K+1$ 개 고른 해가 $K$ 개 고른 해보다 떨어지지 않는다는 것을 증명하는 것과 마찬가지입니다. 이것은 원래 문제를 푸는 것과 유사하게, xoxoxox 를 oxoxoxo 로 변환하는 식으로 이득을 취하는 간선 집합을 지우지 않으면서 $K^\prime$ 만 증가시키면 됩니다.

BOJ 31692. Colourful Tree

알고 있는 $O(n \log n)$ 풀이가 3가지가 있는데, 그 중 가장 깔끔한 방법을 소개합니다. ($q$ 대신 $n$ 으로 표기하겠습니다.)

먼저, 트리의 임의의 두 정점 간 거리를 $O(1)$ 에 계산할 수 있도록 전처리합시다. 초기 입력을 다 받아서 트리를 만들어 놓고, $O(n \log n)$ 전처리, $O(1)$ 쿼리 LCA 자료 구조를 구성하면 됩니다. (LCA를 오일러 투어 상 구간 최솟값으로 구하면 RMQ sparse table로 $O(1)$ 에 값을 계산할 수 있는 것이 잘 알려져 있습니다.)

색깔이 총 한 가지만 있는 버전을 생각해 봅시다. 트리에 $i$ 개의 정점이 있을 때의 지름을 관리하고 있다면, 새 정점 $(i+1)$ 이 들어왔을 때 지름으로 가능한 경우는 단 3가지입니다:

$(i+1)$ 번 정점을 지나지 않는 지름 (기존 지름)
$(i+1)$ 번 정점에서 시작해서 기존 지름의 양 끝점 중 하나에서 끝나는 지름

$(i+1)$ 번 정점에서 시작해서 다른 정점에서 끝나는 경우는, 끝점을 지름의 양 끝점으로 바꿨을 때 거리 손해를 보지 않습니다. (손해를 본다면 지름이라는 가정에 모순입니다.) 고로, 세 경우의 지름을 고려하고 최댓값을 취하면 됩니다. 전처리 포함 $O(n \log n)$ 에 해결됩니다.

색깔이 총 두 가지만 있는 버전을 생각해 봅시다. 각 색깔 $i \in {1, 2}$ 에 대해서, $(u_i, v_i)$ 를 색깔 $i$ 인 두 정점 간 거리 최대 쌍으로 정의합시다. ($i$ 번 색깔 만을 봤을 때의 지름이라고 생각하면 됩니다.) 최적해의 끝점은 각각 색깔 $1$ 과 색깔 $2$ 일 것입니다. 위와 동일하게, $i$ 번 색깔의 끝점이 $u_i, v_i$ 가 아닌 최적해가 존재한다면, 이 끝점을 $u_i$ 혹은 $v_i$ 로 바꿔도 거리 손해를 보지 않습니다. 결국 $(u_i, v_i)$ 만 관리할 수 있다면, 전체 문제를 전처리 제외 $O(n)$ 에 해결할 수 있습니다.

$(u_i, v_i)$ 를 관리하는 것은 색깔이 총 한 가지인 버전이랑 유사합니다. 분할 정복을 사용합시다. 색깔이 $i$ 번인 정점의 집합을 $S$ 라고 합시다. 이 집합을 $S = L \cup R$ 로 나눠서, $L$ 과 $R$ 각각에서 거리 합 최대 쌍을 구했다면, $S$ 에서의 최대 쌍은 $L, R$ 에서 최대 쌍에 속하는 4개 정점에서 시작하고 끝납니다 (증명은 색깔 2개와 동일합니다.) 이제 정점이 추가/제거 되는 상황에서 최대 쌍을 관리해야 하는데, 이는 세그먼트 트리를 사용하면 됩니다. 전체 문제가 $O(n \log n)$ 에 해결됩니다.

사실 색깔 두가지 버전을 해결하면 전체 문제 역시 바로 해결이 됩니다. 모든 $0, 1, \ldots, \log n$ 번째 비트에 대해서, 해당 비트가 켜져있는 색깔을 색깔 1, 꺼져있는 색깔을 색깔 2라고 한 후 색깔이 두 가지인 버전을 $\log n$ 번 풀면 되기 때문입니다. (답이 되는 쌍에 대해서 켜짐 여부가 다른 비트가 무조건 존재하기 때문에 $\log n$ 개의 인스턴스 중 답이 무조건 존재합니다.) 다만 이러면 $O(n \log^2 n)$ 이니 실제로는 이것보다 조금 더 열심히 해야 합니다.

먼저, 각 색깔 $i$ 에 대해서 거리 최대 쌍을 전부 관리하는데, 그냥 세그먼트 트리를 사용하여 관리하면 $O(n^2)$ 의 메모리를 사용하기 때문에 오프라인으로 좌표압축을 해서구현하거나 아예 Treap과 같은 BBST를 사용하여 구해야 합니다. 이를 토대로 $n$ 개의 색깔에 대해 $(u_i, v_i)$ 를 전부 계산했다면, 이제 이를 세그먼트 트리를 사용해서 합쳐줘야 합니다. 구체적으로, 구간 $[L, R]$ 에 대해서, 색깔 $L, L+1, \ldots, R$ 만을 사용했을 때 (거리 최대 / 다른 색깔 쌍 거리 최대) 를 노드로 저장합시다. 거리 최대를 합치는 건 색깔 한 가지와 동일하고, 다른 색깔 쌍 거리 최대를 합치는 건 색깔 두 가지와 동일합니다. 고로 각 노드를 $O(1)$ 시간에 관리할 수 있고, 세그먼트 트리의 루트에는 문제의 정답이 저장됩니다. 시간 복잡도는 $O(n \log n)$ 입니다.

BOJ 28182. Elimination Race

각 선수 $r$ 에 대해서 $r$ 이 이길 수 있는 지의 여부를 따로 판단합시다. $n-1$ 개의 경기와 $n-1$ 명의 선수 ($r$ 제외) 에 대해서, $i$ 번 경기에서 $j$ 번 선수가 $r$ 번 선수에게 진다면, $i \rightarrow j$ 로 가는 간선을 긋습니다. 이렇게 구성된 이분 그래프에서 완벽 매칭이 있음과, $r$ 이 이길수 있음의 여부가 동치임을 증명합니다.

역방향의 증명은 쉽습니다. 만약에 $r$ 이 이길 수 있다면, 올바른 경기 진행의 순열이 있고, 해당 순열에서 탈락하는 선수는 $r$ 한테 무조건 지기 때문에, 각 순열에서 탈락하는 선수를 매칭하면 완벽 매칭을 찾을 수 있습니다.

정방향의 증명은 조금 더 까다롭습니다. $i$ 번 경기에서 탈락하는 선수와 $i$ 번 경기와 매칭된 선수가 일치한다면 좋겠지만, 그런 경기가 없을 수도 있기 때문입니다. $f(i)$ 를, $i$ 번 경기에서 실제로 탈락하는 선수가 매칭된 경기의 번호라고 합시다. $f(i) = i$ 인 경우가 존재한다면, 그냥 이 경기를 플레이하고 경기와 선수를 모두 지워주고 반복하면 됩니다. 이런 경우가 존재하지 않는 경우가 문제인데, 그 경우에는 매칭을 수정해서 이런 경우가 존재하도록 바꿀 수 있습니다. $f(i)$ 를 functional graph로 보면, 이 그래프에는 무조건 사이클 ${c_1, c_2, \ldots, c_k}$ 가 존재합니다 ($f(c_1) = c_2, f(c_2) = c_3, \ldots, f(c_k) = c_1$). 이 사이클 안에서, $c_i$ 번 경기와 매칭된 선수를 $c_i$ 번 경기에서 탈락한 선수로 전부 바꿔주면, $f(c_i) = c_i$ 가 모두 만족하며, 여전히 올바른 완벽 매칭임을 확인할 수 있습니다. 고로, $f(i)$ 를 구한 후, functional graph에서 사이클을 아무거나 찾아서 $f(i) = i$ 인 경기를 만들고 이를 플레이하는 것을 반복하면 됩니다. $f(i)$ 를 (amortized) $O(1)$ 에 구할 수 있도록 유의해서 구현합시다.

이분 매칭을 $F(n)$ 시간에 구할 수 있으면, 전체 문제가 $O(n^3) + n \times F(n)$ 에 해결됩니다. 실라버스 안에 있는 이분 매칭은 $F(n) = O(n^3)$ 이고 시간 초과를 받습니다. 실라버스 밖에 있는 Hopcroft-Karp 이분 매칭은 $F(n) = O(n^{2.5})$ 이며 이것도 시간 초과를 받습니다. 크게 두 가지 상수 최적화가 필요합니다:

인접 행렬을 bitset으로 관리한 후 Naive한 매칭을 쓰는 것이 Hopcroft-Karp보다 빠릅니다. (이론적으로는 Hopcroft-Karp를 사용한 풀이는 $O(n^{3.5})$ 이고 bitset을 사용한 풀이는 $O(n^4 / \log n)$ 이지만, bitset은 정점이 작은 그래프에서 확실한 이점이 있는 반면 Hopcroft-Karp는 BFS/DFS를 $O(n^{1.5})$ 번 해야 해서 최적화에 한계가 있습니다.)
초기 랜덤한 maximal matching을 잡아줄 경우 수행 시간이 크게 향상됩니다.

Faker's algorithm (1)	2024.11.18
IOI 2024 Day 2 (0)	2024.09.15
IOI 2024 Day 1 (0)	2024.09.10
IOI 2018 Problem 6. 모임들 (Meetings) (0)	2024.09.02
SCPC 2024 간략한 풀이 (0)	2024.09.01

구사과