CS Academy Round #72

링크

koosaga님이 작성한 라운드라고 해서 처음으로 참가해 보았다. 먼저 CS Academy의 플랫폼이 굉장히 멋지다는 생각을 했다. Codeforces를 참가하면서, "이런 기능이 있으면 좋겠다, 재미있겠다" 하는 생각을 했었다. CS Academy는 그런 기능들을 모두 가지고 있다. 대표적으로,

- 문제와 소스를 한 화면에 볼 수 있다.

- 웹 상에서 예제를 간단히 돌려볼 수 있다.

- 점수가 푼 사람 수에 따라 유동적으로 변한다.

- 사이트가 예쁘게 생겼다.

- 첫 라운드에서 내가 대박을 쳤다.

좀 쩌는 사이트인데 왜 유명하지 않은가 하는 생각이 든다. CS Academy 짱!

1. Reversed Number

print(1 if (int(x) < int(x[::-1])) else 0) 끝.

2. Circle Kingdom

임의의 두 도시 사이의 거리는 부분합을 사용하면 상수 시간에 구할 수 있다. 그냥 모든 쌍의 거리를 구해서 해결하면 된다. 삼분 탐색을 이용하면 $O(n\log n)$에도 풀 수 있다.

3. Beautiful Matrix

각 열과 행에 대해 양 끝 두 개 엔트리의 1배, 나머지 엔트리의 2배를 합한 결과를 $r_{1..n}$, $c_{1..m}$로 두자. 내부의 각 열/행을 가장자리로 보냈을 때 얻을 수 있는 최대 추가 beauty는 다음과 같다:

$\max(\max(r_{2..n-1}) - \min(r_1, r_n), \max(c_{2..m-1}) - \min(c_1, c_m))$

이 결과가 0보다 작으면 그냥 바꾸지 않는 게 이득이고, 크면 바꾸는 게 이득이다. 원래의 beauty를 계산한 후, 위 값을 더해주면 답을 도출할 수 있다.

4. Spring Cleaning

연결되어 있는 $N$개의 컴퓨터들 가운데 $N-1$개는 무조건 치료할 수 있다. 간선으로 만들 수 있는 경로(무조건 모두를 지나는 경로가 존재한다)의 역순으로 치료하면 된다. 컴포넌트가 모두 사이클인 경우와 그렇지 않은(indegree가 0인 정점이 존재하는) 경우로 나누어 DFS로 풀면 된다.

5. Line Enemies

쿼리 3을 어떻게 풀 지 생각해보자. 웬만한 경우에는 그래프는 거의 완전할 텐데, 경로의 길이가 그렇게 길지는 않을 것 같다. 실제로, 0, 1, 2, 3, -1(경로가 없음) 다섯 가지 경우만 존재한다.

□ 0: A와 B가 같은 구간을 나타낸다.

□ 1: A와 B가 나타내는 구간이 겹치지 않는다.

□ 2: A와 B 모두와 겹치지 않는 구간이 존재한다.

□ 3: 두 구간 중 하나가 다른 하나를 포함하지 않는다. 그리고, $A \cap B$와 겹치지 않고 $A-B$, $B-A$와 겹치는 구간이 각각 1개씩 존재한다.

□ -1: 위 경우들에 해당되지 않는다.

3인 경우가 떠올리기 힘들었다. 위 모든 조건은 시작점과 끝점을 따로 multiset에 집어넣어 계산할 수 있다. 시간 복잡도는 $O(q \log q)$

6. Diamond Dogs

두 구간에 있는 수의 최댓값이 다르면, 무조건 최댓값이 큰 쪽이 더 클 것이다. ($2^n > 2^{n-1} + \cdots + 2^0$) 그러면, 최댓값이 같으면 어떡하지? 이 말은 두 구간이 겹친다는 이야기이다. 두 구간의 교집합을 제거하고 비교하면 정확한 비교 결과를 얻을 수 있다. 이 비교는 최대 원소를 저장하는 구간 트리를 이용해 할 수 있다. 위의 내용을 그대로 정렬의 비교 기준 함수로 사용하여 내장 정렬 함수로 정렬하면 $O(n \log^2 n)$로 해결할 수 있다.

나는 970ms로 간신히 통과했다. 채점하면서 엄청 떨렸다.

7. MST and Rectangles

Boruvka의 MST 알고리즘을 이용해 평면 스위핑으로 푸는 문제이다. 사실상 이 문제를 싣고 싶어서 이 글을 썼다. 갓 문제이다.

Kruskal이나 Prim의 알고리즘은 그래프의 각 간선의 무게를 직접 접근해야 하기 때문에 이 문제를 푸는 데에 적합하지 않다. 사실 이런 특이한 문제 말고는 쓰일 것 같지 않은 Boruvka 알고리즘의 개요는 다음과 같다.

- 각 정점에서 다른 정점으로 나가는 최소 비용의 간선을 찾는다. 이들은 모두 MST에 포함된다.

- 묶인 컴포넌트들을 다시 하나의 정점으로 생각하여, 모든 정점이 한 컴포넌트로 묶일 때까지 위 과정을 반복한다.

각 단계에서 최소 절반의 정점은 연결하므로, Boruvka 알고리즘의 시간 복잡도는 각 정점에서 나가는 최소 비용의 간선을 찾는 시간 $\times O(\log V)$가 된다.

그러면 각 정점에서 나가는 최소 비용의 간선을 어떻게 찾아야 할까? 여기서 라인 스위핑 기법이 사용된다. 우리는 인접 행렬을 위에서 아래로 훑을 것이다. 어떤 정점 $i$에서 나가는 최소 비용의 간선은 인접 행렬의 $i$번째 행의 원소의 최솟값이 될 것이다. 그리고, 직사각형 $(X_1, X_2, Y_1, Y_2)$와 $W$를 $Y_1$행부터 $Y_2$행까지 $[X_1, X_2]$ 구간에 값 $W$를 추가해주는 연산으로 생각하면 이는 $Y_1$ 행에서 "$[X_1, X_2]$에 $W$를 더함" 사건과 $Y_2+1$ 행에서 "$[X_1, X_2]$에 $-W$를 더함" 사건으로 나눌 수 있다. 그러면 이제 지연 갱신(lazy propagation)을 이용한 세그먼트 트리를 쓸 수 있다. 위에서 아래로 쓸어 내려가면서, 이 행에 해당하는 사건들의 연산을 차례대로 수행한 뒤, 이 행의 최솟값을 확인하면 되는 일이다.

마지막 고비는 다음과 같다: 정점 $i$에서 나가는 간선들 중에서, $i$로 돌아오거나 $i$와 같은 컴포넌트에 속하는 정점으로 향하는 간선을 세면 안 된다. 이는 세그먼트 트리의 각 노드에 다음과 같이 값을 추가로 부여해 해결할 수 있다.

- 기존: [최소 비용 $w$, $w$의 위치 $p$]

- 변경: [최소 비용 $w$, $w$의 위치 $p$, $p$와 다른 컴포넌트에 속한 간선들 중 최소 비용 $w'$, $w'$의 위치 $p'$]

그럼 이제 정점 $i$에서 다른 컴포넌트로 나가는 최소 비용의 간선을 구할 수 있다. 간단히 $p$가 $i$와 같은 컴포넌트에 속해 있다면 $p'$를 고르면 되는 것이다. 이와 같이 union-find 등으로 컴포넌트를 묶어 주면서 다른 컴포넌트로 나가는 최소 비용의 간선의 무게만큼을 계속 더해주면 답을 얻을 수 있다.