2021-08-08 Problem Solving

오랜만에 문제 해결을 좀 해봤다.

18227. 성대나라의 물탱크

DFS ordering을 이용하여 트리를 직선으로 펼 수 있다. 구체적으로는, DFS에서 정점 $u$를 처음 방문하는 시각을 $in[u]$, 빠져나오는 시각을 $out[u]$라 할 때, $u$의 서브트리의 방문 시각은  $[in[u], out[u]]$ 범위에 속함을 알 수 있다. 이를 이용하면, 트리를 선형으로 다룰 수 있고, Binary Indexed Tree 와 같은 자료구조를 함께 얹어서 문제를 해결할 수 있다. (왜냐하면, 어떤 정점에 물이 차는 횟수는, 해당 정점을 루트 노드로 하는 서브 트리에 물을 채우려 시도하는 횟수와 같기 때문이다.)

 

참고로, DFS ordering을 이용하여 트리를 직선으로 펴는 테크닉은 여러 분야에 응용의 여지가 있다. 실제로, 데이터 베이스에서 중첩 집합 모델이 이러한 아이디어를 응용한다.

13141. Ignition

일단, 시작점으로 가능한 $n$개의 경우를 모두 따져보자.

 

각 경우에 대해, 먼저 어느 정점에 불이 도달하는 최초 시각을 생각해볼 것이다. 이 시각은, 정확하게, 시작점으로 부터 그래프 상에서의 거리와 같다. 이 시각들을 전부 계산해두었다 가정하고, 정점 $u$에 불이 $T(u)$에 도달한다고 하자.

 

그러면, $u - v$ 정점을 잇는 길이 $w$의 간선이 전부 타서 없어지는 시점은 언제일까? 이를 잘 생각해보면, $\frac{T(u) + T(v) + w}{2}$ 정도가 됨을 알 수 있다. 따라서, 플로이드-워셜 알고리즘을 이용하여 초기에 all pair shortest path를 구해두면, 쉽게 문제를 해결할 수 있다.

16572. Pixel Triangles

입력을 2차원 배열에 미리 받아두자. 구체적으로, $i$행 $j$열을 기점으로 하는 길이 $L$의 삼각형이 주어졌다고 하자. 그러면, $(i, j, L)$이라는 정보를 $(i+1, j, L-1)$, $(i, j+1, L-1)$이라는 정보로 쪼개어 전파해줄 수 있다. 풀이가 다소 깔끔한 언어로 정리되기 쉽지는 않은 것 같은데, 2차원 배열에 입력을 받아두고, 이를 왼쪽 위 칸 부터 차례로 보면서 정보를 전파해나가는 방식으로 문제를 해결할 수 있다.

1937. 욕심쟁이 판다

인접한 칸들 사이에 대나무가 많은 쪽에서 적은 쪽으로 간선을 이어 참조관계를 나타내는 DAG를 만들 수 있다. 이 DAG 상에서 자명한 dp를 통해 문제를 해결할 수 있다.

11670. 초등 수학

왼쪽 정점을 입력 된 수의 쌍, 오른쪽 정점을 정수집합으로 하는 이분 그래프를 생각할 수 있다. 어떤 입력 된 수의 쌍과 그의 연산 결과로 가능한 정수들 사이에 간선을 이어주면 이분 그래프가 된다. 그러면, 결국 문제는 이분 그래프 상에서 최대 매칭을 구하는 문제가 되어 쉽게 해결할 수 있다.

18180. Saba1000kg

어떤 그래프가 초기에 주어지고, 주어지는 각 "정점 집합" 마다 induced subgraph에서 컴포넌트의 수를 세는 문제이다. 이 문제를 제곱 시간보다 빠르게 해결하기 위해, 우리는 주어지는 정점 집합의 크기가 작을 때와 클 때에 다른 접근 전략을 취할 것이다. (기본적으로는 두 경우 모두 유니온 파인드 트리 자료구조를 사용하나, 어느 간선이 induced subgraph에 속하는지 판별하는 과정에서 사용하는 전략이 다르다.)

1. 주어지는 정점 집합의 크기가 작은 경우
   이 경우에는, 모든 정점의 쌍을 보면서 간선이 있는지 확인해줄 수 있다.
2. 주어지는 정점 집합의 크기가 큰 경우
   이 경우에는, 각 간선을 보면서 양 끝점이 모두 주어지는 정점 집합에 속하는지 확인해줄 수 있다.

1의 경우 한 번에 $O(X^2 \log N)$ 정도의 시간이 걸리며, 2의 경우에는 한 번에 $O(M \log N)$ 정도의 시간이 걸린다. (여기에서, $X$는 주어지는 정점 집합의 크기를 의미한다.) 1번 경우와 2번 경우를 나누는 기준을 $X  = \sqrt N$ 정도로 잡아주면, 2번 경우는 최대 $\sqrt N$번 등장하고, 1번 경우도 함수 $f(x) = x^2$이 아래로 볼록하다는 사실을 염두에 두면, 총 $O((N+M) \sqrt N \log N)$ 이내 정도의 시간에 문제를 해결할 수 있다.

16601. Access Points

먼저, $x$축과 $y$축을 별도로 고려해줘도 된다는 자명한 관찰에서 문제의 풀이가 시작된다. 앞에서 부터 정점들을 차례로 본다고 하자. 정점들을 몇 개의 "그룹"으로 나눠 각 그룹별로 하나의 좌표를 할당해줄 것이다. 또 쉽게 관찰할 수 있는 사실은, 어느 그룹이 정해졌다고 했을 때, 각 그룹별로 그룹의 좌표의 평균을 할당해주는 것이 최적임 또한 매우 명백하다.

 

이 때, 어떤 정점이 직전 정점과 같은 그룹에 속할 상황은 무엇일까? 바로, 직전 정점이 속하는 그룹의 좌표 평균보다 해당 정점의 좌표가 작은 상황이다. 그래서, 이렇게 그룹을 지어주고 제출을 하면... WA를 받을 수 있다. 왜냐하면, 이전에 있는 그룹에 할당되는 좌표가 이후에 있는 그룹에 할당되는 좌표보다 작거나 같다는 보장이 없기 때문이다. 따라서, 할당 받는 좌표의 대소 관계가 그룹의 선후 관계보다 역전되는 그룹들을 잘 묶어서 하나의 그룹으로 만들어 줘야 하며, 이를 잘 수행하면 문제를 해결할 수 있다.

 

자명한 관찰을 쌓아서 전체 문제를 해결한다는게 재밌었다.

19649. 미담 전하기

먼저, 사람들이 있는 그래프를 SCC로 나누어 생각할 수 있다. 그러면, 미담 당사자가 속하는 SCC로 도달할 수 있는 시작점들을 생각해볼 수 있고, 이 정점들은 미담 당사자와 같은 SCC에 속하거나, 혹은 해당 SCC로 (위상정렬 스러운 의미에서) "올 수 있는" SCC에 속할 것이다. 이제, 각 SCC들을 정점으로 압축해서 DP를 통해, 각 SCC에서 시작해서 미담 당사자가 속하는 SCC로 갈 때 거칠 수 있는 정점의 최대 개수를 구해줄 수 있다. 이 정보를 이용하면, 직접 미담 전파자를 잘 결정하여 문제를 해결해줄 수 있다.

 

덧: 개인적으로는 디스크립션이 약간 어려웠다.