RUN@KAIST 7/5 방학 연습 풀이

1. Kralj

원형 구조에서 푸는 문제들은 그대로 풀면 짜증나거나 어려운 경우들이 많기 때문에 선형 구조로 환원시키는 것이 중요하다. 이 문제에서도 그러한 것이 가능하다. 어떠한 자리 i에 대해서, 어떤 몬스터들은 그 자리에 앉기 위해 달려들 것이고, 어떤 몬스터들은 그 자리에 실제로 앉을 것이다. flux(i) = (i번째 자리에 앉으려고 온 몬스터의 수) - 1이라고 하자. 1은 그 자리에 실제로 앉아서 싸우는 몬스터를 뜻한다. 

flux(i)의 부분합을 한번 그래프로 그려보자. 0점에서 올라갔다 내려갔다 했다가 다시 0점으로 오게 될 것이다. 이 중 최소를 찍는 위치가 있는데, 여기를 중심으로 왼쪽과 오른쪽 구간을 바꿔보자 (cyclic shift). 그렇다면, 이 그래프는 0점에서 올라가다가 내려가다가 다시 0점으로 오게 될 것인데, 한번도 0 미만의 값을 가지지는 못할 것이다. 여기서 어떠한 몬스터가 n번 점에서 1번 점으로 쫓겨나는 것이 가능할까? 그 전에 항상 자리를 찾게 되어서, 그러한 일은 일어날 수 없다. (말로 설명하기 너무 어려운데, 이 부분합을 "해당 위치에서 몇 마리의 몬스터가 쫓겨나는지" 로 생각하면 이해가 쉽다. 부분합에 invalid한 값이 없게 (음수가 없게) 조정을 했다면, 결국 마지막 위치는 0마리의 몬스터가 쫓겨난다는 것을 알 수 있다.)

고로, n번 점과 1번 점은 독립적이니 선형 구조에서 문제를 풀 수 있다. 이는 1번 점에서 시작해서 그리디하게 해결하는 것이 최선이다. 싸울 수 있는 몬스터 중, 이길 수 있는 몬스터가 있다면 그 중 가장 강한 놈과 싸워서 이기고 , 그렇지 않다면 가능한 몬스터 중 제일 강한 놈과 싸워서 진다. 이렇게 해결할 시 정답을 받을 수 있다.

2. CSS

HTML 문서의 요소들이 가지는 계층적인 구조는 트리로 모델링할 수 있다. 고로 주어진 HTML 문서를 스택이나 재귀적 함수를 통해서 트리 형태로 정리하고, 정리된 구조에서 주어진 질문을 해결하면 된다. 

주어진 질문들이 전부 단순 구현으로 해결 가능하기 때문에, 질문과 문서에 대한 parser를 구현해서 문제를 해결할 수 있다. 트리인 점을 간파하는 것 외에 특별히 알고리즘적인 복잡함은 없다. 하지만 파싱이 꽤 복잡한 편이니, 구조화를 잘 해야 한다.

3. Acrobat

문제에서 주어진 연산을 사용해서, 모든 간선을 한번씩만 방문할 수 있는, 즉 오일러 회로가 있는 그래프를 만들어야 한다. 그래프가 오일러 회로가 있기 위해서는, 모든 정점의 차수가 짝수여야 하며, 차수가 0 초과인 정점들이 모두 연결되어 있어야 한다. 여러 방법이 있겠지만, 우리는 여기서

 * Type 1 연산을 통해서 모든 A 정점의 차수를 짝수로 만들고

 * Type 2 연산을 통해서 그래프를 연결시키고 모든 B 정점의 차수를 짝수로 만드는

전략을 사용해 보자.

Type 1 연산을 사용할 때는, Ai - Bj 정점이라는 건 신경쓰지 말고 그냥 i - j 정점이 연결된 그래프를 그려보자. 만약에 해당 정점의 A_i degree가 홀수라면 marking을 해 둔다. 간선을 뒤집는 것은, 간선의 양 끝 에지의 marking을 0->1, 1->0으로 바꾸는 것과 같다. 각각의 컴포넌트에 대해 marking된 정점의 개수가 홀수라면 답이 없다.

그렇지 않다면, 컴포넌트의 임의의 spanning tree를 생각해 보자. 리프를 하나 하나 지워나가면서 전체 트리를 정점 하나로 줄일 것인데, 만약에 현재 지우는 리프가 marking이 1이라면, 리프와 그의 부모를 잇는 간선을 뒤집어야 할 것이다. 이러한 식으로 모든 노드를 지우면 마지막 남은 정점 하나의 marking은 무조건 0이다. 실제 구현시에는 union-find를 사용해서 spanning tree에 속하지 않는 간선은 아주 무시해 버리고, 재귀 함수를 통해서 bottom up으로 이 과정을 구현해 준다. 스패닝 트리에 속하는 간선의 개수가 N-1개이니, 많아야 N-1번의 연산으로 A번 정점의 degree가 모두 짝수가 된다. 

이제 Type 2 연산을 사용하는 것은 쉽다. union find를 통해서 연결 안 된 B 정점 쌍들을 연결해 주고 (1 - 2, 1 - 3, 1 - 4...), 그 후 B 정점들 중 홀수 차수를 가진 정점들에 단순하게 에지를 더해주면 된다. 고로 최대 3N/2번의 연산이 필요하다. 합하면 5N/2번의 연산으로 문제를 해결할 수 있다.

4. Explore space

레이저가 들어오는 때마다 그때 그때 방사능 층을 제거하는 접근보다는, 각각의 방사능 층이 끝까지 살아남는지 아닌지 여부만을 판단하는 것이 훨씬 생각하기 간단하다. 방사능 층이 살아남는지 여부는, 주어진 각도 구간 내에 레이저가 있는 지 없는 지를 판별하는 것과 같다. 모든 레이저들을 각도 순으로 정렬하고, 이분 탐색을 통해서 이를 해결할 수 있다. 

C++ 사용자라면 lower_bound, upper_bound, 그 외의 언어에서도 내장된 이분 탐색 함수를 사용해서 쉽게 구현할 수 있다. CCW 함수를 comparator로 넣어 주면 되기 때문이다.