RUN@KAIST 8/15 방학 연습 풀이

1. Arrays

두 행과 열을 바꾼다는 것이 무슨 뜻인지 먼저 생각해 보자. 각각의 행과 열에 대해서 순열 P[i]와 Q[i]를 정의하자. P[i] = (현재 i번 행의 원래 위치), Q[i] = (현재 i번 열의 원래 위치) 라고 하면, 두 행을 바꾸는 것은 단순히 P[i]와 P[j]를 바꾸고, 열을 바꾸는 것은 단순히 Q[i]와 Q[j]를 바꾸는 것이다. 고로 우리가 주어진 연산으로 할 수 있는 것은 P와 Q를 임의의 순열로 섞는 것이니, A와 B가 닮았다 (alike) 는 것은 A[P[i]][Q[j]] = B[i][j] 를 만족하는 순열 P, Q가 존재한다는 것과 동치이다.

모든 수가 다르니, 각 수가 A에서 어떤 위치, B에서 어떤 위치에 있는지를 유일하게 결정할 수 있다. 즉 P[i] = j, Q[i] = j와 같은 등식들이 여러 개 주어진다는 것이다. 등식에 맞춰서 P와 Q를 대입한 후, 모순 없이 순열이 나오는지를 검사해 주면 선형 시간에 해결할 수 있다. 숫자의 절댓값이 작으니 2백만 정도의 배열을 잡아서 구현해 주면 된다.

BOJ 시간 제한이 잘못 설정되어 있어서 FastIO를 써야지만 해결할 수 있는 문제이다. 일단 요청은 넣었는데 바뀔 지는 잘 모르겠다..

2. 도로 건설

동적 계획법으로 문제를 해결해 보자. 간선을 전부 만든 후 우리가 신경써야 하는 제약 조건은 1. 간선 개수가 M개여야 하며 2. 모든 정점의 degree가 짝수여야 한다 는 것이다. 첫번째 조건은 상태에 넣을 수 있지만, 두번째 조건은 각 degree의 홀짝성을 모두 넣으면 상태가 2^N이 되어서 힘들어 진다. 고로 새로 만드는 간선의 |A - B| <= K라는 점을 활용해서 이 상태를 2^K 정도로 줄여야 한다. 

이를 위해서 간선을 (2, 1) / (3, 1) / (3, 2) / (4, 1) / (4, 2) / (4, 3) .... / (N-K, N) / (N-K+1, N) / (N-K+2, N) ... (N-1, N) 과 같은 순서로 건설하자. (j, i) 간선을 추가할 때, 번호 i+1 이상의 정점은 아직 건설이 전혀 되지 않았고, 번호 i - K 미만의 정점은 더 이상 손을 쓸 수가 없다는 것을 (고로 올바른 상태면 짝수여야 함을) 알 수 있다. 고로 이 때 [i-K, i] 구간의 degree의 홀짝성만 비트마스크로 관리하고 있으면 된다. 이 점을 관찰하면 DP의 상태가 DP[j, i, 사용 간선 수, 비트마스크] 와 같이 정해진다. (j, i) 간선을 몇 개 추가하는지를 고정시키면서 동적 계획법을 돌리면 O(NM^2K * 2^K) 정도에 문제를 해결할 수 있다.

이해가 안 된다면 https://pstopia.github.io/src/tc/srm532d1-2/ 를 참고해도 좋다.

3. Moving to Nuremberg

문제를 요약하면 가중치 있는 트리에서 각 정점 i마다 f_i라는 값이 주어졌을 때 각각의 정점 i에 대해서 sum(dist(i, j) * f_j) 를 계산해야 하는 것이다. 다양한 풀이가 있고, 그 중 내 풀이는 다음과 같다. 

i에 대해서 sum(dist(i, j) * f_j) 를 계산하는 것을, j가 서브트리 안에 있는지 밖에 있는지로 나눠서 DP를 사용한다. DP1[i] = (i의 서브트리 안에 있는 j들에 대해서 sum(dist(i, j) * f_j)), DP2[i] = (i의 서브트리 안에 없는 j들에 대해서 sum(dist(i, j) * f_j)) 와 같은 식이다. 

DP1[i]를 계산하는 것은 다음과 같이 가능하다. 리프에서 부모로 올라가면서 계산하는데, i의 각 자식 w에 대해서 DP1[w]가 계산되어 있으면, i에서 w의 서브트리 안에 있는 정점과의 거리 합은, w에서 w의 서브트리 안에 있는 정점과의 거리 합에, (i - w 에지 길이)가 일정 횟수만큼 추가된 형태일 것이다. 식을 써보면 이 일정 횟수는 w의 서브트리 안 f의 합이고, 고로 w의 서브트리 안에 있는 정점과 i와의 거리 합을 구할 수 있다. 이를 모든 자식에 대해서 해주면 DP 테이블 전체를 O(n)에 채울 수 있다.

DP2[i]도 큰 차이는 없다. 이것은 부모에서 리프로 내려가면서 계산하는데, i의 부모 p에 대해서 DP2[p]가 계산되어 있다고 하자. p의 서브트리였지만, i의 서브트리가 아닌 정점들을 먼저 추가해야 하고, 추가로 p - i 에지 길이도 일정 횟수만큼 더해진다. p의 서브트리이면서 i의 서브트리가 아닌 정점들의 거리 합은 DP1[p]와 DP1[i]에 대한 식으로 나오고, p - i 에지 길이가 추가되는 횟수는 w의 서브트리 밖 f의 합이다. 이렇게 하면 DP 테이블 하나를 O(1)에 채울 수 있다. 고로 DP1[]와 DP2[]가 O(n)에 채워진다. 모든 거리 합은 DP1[] 과 DP2[]의 합이니 이것을 토대로 문제의 질문에 답하면 된다. 서브트리 안에 있는 정점 합, 밖에 있는 정점 합을 나눠서 DP를 하는 것은 트리 DP 문제를 풀 때 유용한 접근 방식이니 참고해 두면 좋다. 

centroid를 찾듯이 구현하는 방법도 있었고, DP를 조금 다르게 정의한 경우도 있었다. DP 정의가 약간 다른 풀이는 http://jh05013.blog.me/221074984117 를 참고하자. 

4. Farmland

평면 그래프가 주어졌을 때, 그래프 안에 있는 영역(face) 중 정점의 개수가 k개인 것을 세는 것이다. 모든 영역을 나열하고, 그 영역의 정점 수가 k개인지를 세는 접근을 취할 것이다. 평면 그래프의 각 영역을 탐색하는 것은 Dual graph를 구하는 등 (예시 : 대전 2016 A, IOI 2007 Flood, 함수컵 Masonry Bridge) 평면 그래프를 쉽게 다루고자 할 때 굉장히 유용하다. 알고리즘이 복잡하진 않지만 기하 알고리즘같이 실제로 구현을 해 봐야 이해하기 쉽다.

각 영역을 탐색하는 방법은 다음과 같다. 대충 각각의 face를 시계 반대방향으로 탐색한다 생각하면 된다. 먼저 방문하지 않은 간선의 한 방향을 잡고 시작하자. 해당 간선의 왼쪽 영역(face)를 탐색할 것이다. 간선의 끝점에서, 해당 간선의 왼쪽 영역과 맞닿아 있는 (즉 시계 방향으로 돌리면 나오는) 간선을 찾아서, 해당 간선에서 이를 반복한다. 이를 계속하면 처음 시작한 간선이 나올 것이고 이 때 영역의 탐색이 끝나게 된다. 이를 모든 간선의 모든 방향에 대해서 처리해 주면 된다. 

구현을 할 때는, 각각의 정점에 대해서 나가는 간선들을 각도 순으로 정렬하자. 현재 s -> e 간선을 타고 들어왔다고 하면, e -> s 간선의 시계방향으로 인접한 간선이 다음 간선이 될 것이다. 이를 O(V) 정도에 나이브하게 계속 찾아주면 O(VE) 시간 복잡도에 문제를 해결할 수 있다. 간선에 대한 visited 배열을 잡아야 하는데 입력이 작아서 대충 이중 배열을 잡아도 된다. 

평면 그래프는 E <= 3V - 6을 만족한다. 고로 이 알고리즘은 O(n^2)이고 시간 안에 충분히 작동한다. 몇가지 정보를 더 저장해 두면 (s -> e 간선의 역간선이 어디 있는지 등등) 이 알고리즘을 준 선형, O(nlgn) 정도로 줄일 수도 있다.