Problem Solving Diary #3

지인 분들에게 추천받은 문제들을 풀어 보았습니다.

 

BOJ 12963. 달리기

번호가 큰 간선부터 보면서, 해당 간선 용량만큼의 사람을 추가로 보낼 수 있는지 판별합시다. 이때 남은 간선들을 통해 시작점에서 끝점까지 모든 간선의 용량이 $3^i$ 이상인 경로를 만들어야 합니다. 이러한 경로가 존재하지 않으면 사람을 보낼 수 없습니다.

 

$3^0 + 3^1 + \cdots + 3^i < 3^{i+1}$이기 때문에, 용량이 큰 간선을 직접 사용하지 않는 이상 용량이 더 작은 간선들에 의해 막히는 일이 없습니다. 따라서 용량 큰 간선을 최대한 취하는 것이 최적 전략이고, Union Find 자료구조를 이용해 시작점에서 끝점까지 경로가 존재하는지 판단해 주면 됩니다. 나이브하게 짤 경우 $O(NM)$, Union Find Rollback을 이용할 경우 $O(M \log N)$에 풀 수 있습니다.

 

BOJ 21216. Emails

그래프의 두 정점 $(u, v)$ 간 최단경로의 길이 중 가장 긴 것을 $d$라고 할 때, $d$를 상대오차 2 이내로 찾아야 하는 문제입니다. 트리나 그래프에서 경로의 길이가 주어지고, 상대 오차 2 이내라는 조건이 주어지면 접근 방향은 정해집니다.

 

아무 정점(정점 1)을 잡은 뒤, 해당 정점에서 bfs를 돌려 가장 먼 정점까지의 거리 $d'$를 잡습니다. 자명하게 $d' \le d$입니다. 또한 거리가 $d$인 두 정점 $u$, $v$ 사이 거리는 $dist(u, 1) + dist(1, v) \le 2d'$ 이하여야 하므로 $d \le 2d'$입니다. 따라서 $1 \le \frac{d}{d'} \le 2$를 만족합니다.

 

BOJ 22359. 흔한 타일 색칠 문제

잘 알려진 방법으로 타일링을 하고, ㄱ자 타일의 중앙점 위치에 따라 중앙점 위치의 x좌표, y좌표를 4로 나눈 나머지가 (1, 1)이나 (3, 3)일 경우 A, (1, 3)이나 (3, 1)일 경우 B, 기타의 경우 C로 색칠하면 맞습니다. 증명은 어렵지 않습니다. 각 타일의 중앙점의 x좌표와 y좌표를 4로 나눈 나머지가 몇 종류밖에 되지 않는다는 관찰부터 시작하면 됩니다.

 

BOJ 20348. Destabilized Drone

지평선과 $x=1$, $x=W$의 교점을 이분 탐색으로 20회 안에 찾습니다. 그러면 모든 정수 $n$에 대해 $x=n$과 지평선의 교점의 y좌표를 $[h_n, h_n+1)$의 구간 내(즉 절대 오차 1 이내)로 구할 수 있습니다. 따라서 만약 $x=n$과 지평선의 교점의 $y$좌표가 정수라면, 그 후보 값이 하나로 추려집니다. 이제 이 후보들을 모두 시도해 보는데, 가장 왼쪽 후보와 가장 오른쪽 후보를 선형 탐색으로 구하면 여기에 사용되는 쿼리는 $\frac{2}{3} \times 1000$회 이내가 됩니다.

 

BOJ 2261. 가장 가까운 두 점

혼자서 생각하기에는 어렵다고 보이는 분할 정복 문제입니다. 아이디어가 상당히 특이한데, 분할 정복에서 분할된 양쪽 모두에서 한 점씩 고르는 경우를 빨리 해결해야 합니다. 이를 위해 후보를 "쳐내는" 작업이 필요합니다. 왼쪽 그룹과 오른쪽 그룹에서 찾아낸 최단거리를 $d$라고 합시다. 일단 왼쪽과 오른쪽을 가르는 중앙 선에서 $d$ 이상 떨어진 점들을 빼낼 수 있습니다. 이들은 어떻게 묶어도 거리가 $d$보다 작아지지 않습니다. 남은 점들 사이에서 답을 찾아 봅시다. 일단 같은 그룹 내에 있는 점은 모두 $d$ 이상 떨어져 있으므로, 한 점을 고정하고 그 점부터 위로 후보 점들을 모두 보았을 때 $y$좌표 차이가 $d$ 이상으로 넓어지는 시점이 빠를 것이라고 추측할 수 있고, 실제로 7개 점 내에 이러한 상황이 일어납니다.

 

설명이 매우 이상한데, 다른 블로그(https://casterian.net/archives/92)를 둘러보시면 좋을 것 같습니다.