Eau de Cologne
10주차 연습 (3) 본문
D5~ 문제들을 작성합니다.
https://www.acmicpc.net/problem/19297
19297번: Logistical Metropolis
첫 번째 줄에 두 정수 $N$, $M$($1 ≤ N ≤ 100\,000$, $N-1 ≤ M ≤ 300\,000$)이 공백 하나로 구분되어 주어진다. 다음 $M$개 줄의 각 줄에는 건설 가능한 워프 게이트의 정보를 나타내는 세 정수 $x$, $y$, $c$($
www.acmicpc.net
풀이
처음에 Minimum Spanning Tree를 만듭니다. 이 이후에 무조건 사용되는 간선(여기서는 i번과 모두 연결된 간선)이 $k$개 정해졌을 때, 이 계산을 $\tilde{O}(k)$ 안에 하는 문제입니다. 각 정점마다 정점 차수만큼의 간선을 지정하고, 모든 정점에 대해 더하면 총 $2M$개임을 알 수 있기 때문에, 총 시간복잡도를 전처리에다가 쿼리 총 $\tilde{O}(M)$ 시간이 걸리도록 문제를 해결할 수 있습니다.
어떤 간선을 무조건 포함하는 MST를 구하는 방법은, Kruskal 알고리즘에서 해당 간선을 미리 Union해 놓는 것입니다. 해당 간선은 어떤 우선순위보다 높게 사용됩니다. 이것을 이용해서, 우리는 해당 정점을 미리 Union한 상태에서 Kruskal을 빠르게 돌릴 것입니다.
무조건 사용되는 간선을 제외한 나머지 간선은 모두 MST에서 오기 때문에, MST를 기준으로 생각합니다. 우리가 관심을 가지는 정점과 간선에 관련된 부분 이외에는 전부다 MST에 있는 간선을 그대로 사용하기 때문에 트리 압축을 사용해서, 우리가 관심을 가지는 정점과 간선을 추려냅니다.
여기서 간선의 가중치는 정점중에 최댓값을 사용합니다. $u$와 $v$의 경로만 남겨 놓고 $u$와 $v$를 잇는 (가상의) 간선을 무조건 포함하는 MST에서 삭제되는 간선은 $u$와 $v$의 경로중의 최댓값이기 때문입니다.
이제, 새로운 트리의 가중치합은, (원래 그래프의 MST) + (새로 추가한 간선 가중치 합) - (끊어주는 간선 가중치 합)이고, 끊어주는 간선 가중치 합은, 일단 모든 간선을 전부 다 끊은 다음에 MST를 Kruskal로 만드는 과정에서 합쳐주는 방식으로 구하면 됩니다.
MST, LCA등의 전처리에 $O(M \log M)$, 트리 압축에 $O(k \log N)$의 시간이 사용되므로, 사용되는 총 시간은 $O(M \log M)$입니다.
코드: https://www.acmicpc.net/source/share/046ad34df7034bc4ae99047119ed51e8
https://www.acmicpc.net/problem/1659
참고: https://www.acmicpc.net/problem/20077 https://www.acmicpc.net/problem/1628
1659번: 수 (Hard)
첫째 줄에 S의 원소의 개수와 T의 원소의 개수가 빈 칸을 사이에 두고 주어진다. 둘째 줄에는 S의 원소, 셋째 줄에는 T의 원소가 첫째 줄에 주어진 개수만큼 빈 칸을 사이에 두고 증가하는 순서대
www.acmicpc.net
풀이
핵심적인 관찰을 해 봅시다. 최적인 답을 기준으로 합니다. 구간은 S와 T를 연결했을 때, S이상 T이하의 수직선 상의 선분을 말합니다.
- 연결해서 그래프 꼴로 나타내었을 때, 길이 $3$의 경로는 만들어지지 않는다.
- S-T-S-T 꼴의 경로가 존재하면, 가운데의 T-S를 끊어도 됩니다.
- 두 구간은 서로 완벽히 포함하거나, 서로소입니다.
- 수 범위 S1~T1과 S2~T2가 겹친다고 합시다. S1, T2, T1, S2와 같이 연결 되어 있으면, S1-T2; T1-S2가 더 좋은 답입니다. S1, S2, T1, T2와 같이 연결되어 있으면, S1-T2; S2-T1과 같이 연결하는 식으로 경로의 길이를 바꾸지 않고 좋은 답을 낼 수 있습니다.
- 어떤 다른 범위에도 포함되지 않는 구간 S1<T1에 대해서, 내부에 T2<S2꼴의 구간은 존재할 수 없습니다.
- 만약 존재한다면, S1 ~ T2; T2 ~ S1꼴로 나눌 수 있습니다.
- 어떤 연결 성분의 구간에 있는 수가 S...S T...T S...S 꼴이라고 합시다. 가운데 T는 정확히 하나만 존재할 수 있습니다.
- 만약에 어떤 T가 존재해서 왼쪽의 S와 오른쪽의 S를 잇는다고 합시다. 가운데 T가 2개 이상이면 왼쪽 혹은 오른쪽의 T를 더 가까운 곳으로 옮겨주면 문제를 해결할 수 있습니다.
- 우리가 고려해야할 연결 성분은 S...S T...T 혹은 S...S T S...S 꼴 뿐입니다.
- S, T, S, T 형태가 있으면 서로 연결성분이 아닙니다. 한 종류의 수만 있으면 서로 연결될 수 없습니다. 이제 S, T형태와 S, T, S 형태만 남았는데, 위 관찰로 T가 정확히 하나만 존재합니다.
이제 각 연결의 비용을 생각해 봅시다.
- S...S T...T
- 모든 S는 T와 연결되어야 하므로, 적어도 가장 오른쪽 S까지는 선분을 뻗어야 합니다. 마찬가지로 모든 T는 S와 연결되어야 하므로, 적어도 가장 왼쪽 T까지는 선분을 뻗어야 합니다.
- S와 T사이에는 선분이 최소 max(S, T)개만큼 있어야 합니다.
- 이를 만족하는 연결 방법은 S와 T를 밖에서부터 연결하고, 나머지를 가장 안쪽의 원소와 연결하는 것이 있습니다.
- S...S T S...S
- 연결 방법이 유일합니다.
이래서 우리는 $O(N^2)$ 동적계획법을 사용할 수 있고, 20077번 문제 같은 경우에는 30점을 맞을 수가 있습니다. (확인해봐야하는 구간이 많지 않아, Subtask 3을 맞을 수 있습니다.)
이제, 같은 집합에 속한 원소끼리 모은 것을 블록이라고 합시다. 해당 블록의 원소에 대한 동적 계획법 값은, 현재 블록의 어떤 값도 참조하지 않으며, 이전(S...S T...T) 혹은 두 번 이전 (S...S T S...S) 블록의 정보만 참고합니다. 그렇기 때문에, 우리는 블록단위로 값을 업데이트 해 줄 수 있습니다.
만약 이전 블록의 길이가 1이라고 합시다. 이 경우에 왼쪽 S블록의 연결 방법은 유일하기 때문에 (T에 연결), 왼쪽 S...S 블록과 T까지 연결한 전체 비용의 최솟값을 사용해서 오른쪽 S블록의 값을 업데이트 해 줄수 있습니다.
만약 이전 블록의 길이가 2 이상이라고 합시다. 이 경우에 코스트에서 처리하기 가장 힘든 경우는 max이므로, S가 더 많은 경우와 T가 더 많은 경우를 나눠서 생각합니다.
S가 더 많은 경우에는 S의 위치가 정해지면, S 내부 연결 비용, S와 T사이 연결 비용을 알 수 있습니다. 업데이트할 T 블럭에 따라서 S가 더 많은 경우의 비용 중 최솟값을 이용해, T블럭 내부 연결 비용을 더해서 동적 계획법 테이블을 업데이트 할 수 있습니다.
T가 더 많은 경우에는 S의 위치가 정해지면, S 내부 연결 비용을 알 수 있습니다. 업데이트할 T블럭에 따라서 T가 더 많은 경우의 비용 중 최솟값을 이용해, T블럭 내부 연결비용과 S와 T사이 연결비용을 더해서 동적 계획법 테이블을 업데이트 할 수 있습니다.
한 블럭은 최대 3번 참조되고, 모든 동작은 선형적이기 때문에, 시간복잡도는 $O(N)$입니다. (정렬 같은 경우도 오름차순으로 주어지기 때문에, merge를 사용하면 더 빠릅니다.)
코드: https://www.acmicpc.net/source/share/29a0fe7adf2447c5801a6039d9b48d4e
https://www.acmicpc.net/problem/20030
20030번: 트리와 쿼리 17
$N$개의 정점으로 이루어진 트리가 있다. 정점은 1번부터 $N$번까지 번호가 매겨져 있고, 1번 정점은 루트이다. 각 정점 $i$에는 정수 $A[i]$가 저장되어 있다. 가장 처음에 $A[i]$는 0이다. 다음과 같은
www.acmicpc.net
풀이
이후 작성
https://www.acmicpc.net/problem/25019
25019번: 날다람쥐
$N = 3$이고 $1$번 기둥에서 $2$번 기둥까지의 거리는 $2$, $1$번 기둥에서 $3$번 기둥까지의 거리는 $5$, 기둥들의 높이는 왼쪽부터 각각 $8$, $5$, $5$, 기둥들의 가중치는 왼쪽부터 각각 $3$, $4$, $6$, $L=5$,
www.acmicpc.net
풀이
이후 작성
https://www.acmicpc.net/problem/15978
15978번: 족보
표준 입력으로 다음 정보가 주어진다. 첫 번째 줄에는 첫 번째 족보의 사람 수 N1, 두 번째 족보의 사람 수 N2, 각 족보에서 자식이 없는 사람들의 수 K가 주어진다. 첫 번째 족보의 사람 들은 1부
www.acmicpc.net
풀이
이후 작성
https://www.acmicpc.net/problem/18802
18802번: Bridge Construction
첫 줄에 섬의 수 N과 X가 주어진다. (1 ≤ N ≤ 3000, 109 ≤ X ≤ 109+104, X는 소수) X의 용도는 출력 부분을 참고하자.
www.acmicpc.net
풀이
이후 작성
https://www.acmicpc.net/problem/18438
18438번: LCS 5
LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다.
www.acmicpc.net
풀이
이후 작성
'acmicpc.net' 카테고리의 다른 글
| [BOJ 19669] Firefighting (0) | 2023.04.17 |
|---|---|
| [08/26] 문제 + 풀이 + 그림 (0) | 2022.08.26 |
| 10주차 연습 (2) (0) | 2022.06.26 |
| 10주차 연습 (1) (0) | 2022.06.26 |
| 9주차 연습 (0) | 2022.06.26 |