이번 주에는 4문제를 받아서 4문제 모두 풀었다. 아는 문제들이 많이 보였지만 나름대로 생각도 해보고 구현도 해볼 수 있는 셋이었다. 이번 주차는 문제를 푼 순서대로 간단하게 풀이와 생각을 적어 보았다.
사무실 이전 (#)
우선 문제를 좀 더 단순하게 생각할 필요가 있다. 총합을 구하는 것이 목표이므로 문제를 "트리 위에 빨간점이 M개, 파란점이 K개 있을 때 서로 다른 색의 끝 점을 갖는 모든 경로의 길이 제곱의 합"과 같은 식으로 생각하도록 하자. 제곱이라는 조건이 생각하기 어려울 수도 있지만, 이는 (a+b)^2 = a^2 + b^2 + 2ab라는 간단한 식으로 해결해줄 수 있다. 경로들에 대한 문제이므로 센트로이드 디컴퍼지션을 해야겠다고 생각했다. 그럼 각 단계에서 센트로이드를 지나는 모든 경로를 봐주면 되고, 각 점들에 대해 센트로이드까지의 거리, 거리의 제곱을 구해주면 된다. 이를 서브트리별로 합쳐 개수, 길이의 합, 길이 제곱의 합을 두 색깔에 대해 따로 구해두면 위의 식을 이용해 결과를 빠르게 합칠 수 있다. ab항의 합을 계산하는게 헷갈릴수 있지만 두 집합의 모든 쌍의 곱의 합은 각 집합의 합의 곱이므로 어렵지 않게 할 수 있다.
따라서 최종 시간 복잡도 O(N log N)으로 문제를 해결하였다. 사실 센트로이드 없이도 dfs한번에 제곱을 푸는 아이디어를 쓰면 O(N)에 그대로 풀 수 있다. 지난 Trous de loup에서도 그렇고 자꾸 필요없는 로그를 붙이는 것 같다. 하지만 둘 다 굉장히 빨리 풀이를 떠올려서 짰고 내가 생각하기 편한 방식이기 때문에 그랬던 것 같다.
Two Buildings (#)
앞쪽 건물로 쓰일 수 있는 집합과 뒤쪽 건물로 쓰일 수 있는 집합을 뽑아놓고 생각하자. 뒤쪽 건물로 쓰일때는 값이 클수록, 뒤에 있을 수록 좋다. 따라서 자신보다 뒤에 있으면서 높은 건물이 있는 점들은 고려할 필요가 없다. 이렇게 뒤쪽 건물의 후보를 뽑아놓고 나면, 위치가 증가함에 따라 높이가 감소하게 된다. 앞쪽 건물도 마찬가지로 뽑으면 앞쪽은 반대로 높이가 증가한다. 이 단조성에 의하여 DNC opt를 사용할 수 있고 그대로 사용해주면 각 집합을 뽑는 부분이 O(N), DNC가 O(N log N)으로 문제가 풀린다.
DNC opt에 대한 증명은 그냥 각 집합에서 두개씩 뽑고 교차할 때와 아닐때를 식으로 써서 비교하면 정리했을 때 단조성에 의해 성립함을 알 수 있다. 보자마자 직관적으로 풀이가 DNC 테크닉을 요함을 알 수 있었고 이런 테크닉적인 부분은 꾸준히 공부를 해서 앞으로도 익숙해져야 할 것 같다.
JOI 2016 단층 (#)
가장 먼저 생각해야 할 것은 거꾸로 생각하는 것이다. 최종 위치가 특정 점이기 위해서는 마지막 변동 전에 어디에 있어야 하는지를 뒤에서부터 계속해서 역산하면 문제를 쉽게 접근할 수 있고 O(NQ) 풀이가 나온다. 이제 전체 판을 45도 돌리고 생각해보자. 오른쪽 아래가 지표면의 1위치이고 왼쪽 위로 올라가면서 지표면이 이어져 있고, 오른쪽 위 방향이 땅속 방향이 되도록 좌표를 변환하면, 각 변동이 x좌표가 일정 이하인 점들의 y좌표를 증가시키거나, y좌표가 일정 이하인 점들의 x좌표를 증가시키는 연산임을 알 수 있다. 이제 문제를 자료구조를 이용해 풀 수 있다. 구체적으로, 저 변환을 아무리 행해도 지표면을 나타내는 점들의 단조성이 깨지지 않기 때문에 구간 업데이트로 계속 쿼리를 처리할 수 있다. 나는 펜윅으로 이분 탐색과 업데이트를 해서 최종 시간복잡도 O(Q log N)에 해결했다.
솔브드 다3으로 되어있는데 솔직히 그보다는 쉬운 것 같다. 코드가 매우 깔끔하고 환원을 잘 하면 풀리는 문제였다. 펜윅 이분탐색은 알아두면 좋은 테크닉인 것 같다.
소각로 (#)
풀이는 몹시 간단하다. 쓰레기의 대기열은 종류와 개수의 페어로 말그대로 그냥 큐, 또는 덱으로 관리하면 된다. 소각로의 내부는 세그먼트 트리나 std::set등을 이용해서 적당히 구간을 칠할 수 있으면 된다. 네 종류의 쿼리는 이 두가지를 이용해 모두 적당히 처리하면 된다. 적당히 처리한다는 말보다 정확히 설명할 방법이 없다. 코딩을 열심히 하면 되는 문제이다. 나는 set을 사용하여 문제를 해결하였고, iterator 다루기가 귀찮아서 상당히 짜증나는 코딩을 했다. 최종 시간 복잡도는 O(N log N)이다.
사실 이 문제는 원래 알고 있었던 문제이고 전에 풀이 생각까지 마쳤던 문제이다. 그러나 짜기 싫어서 버려두었던 문제이고 이번 셋에서도 끝까지 미뤄두다가 결국 마지막에 풀게 되었다. 다 짜고나니 생각보다는 코드가 짧아서 다행이라고 생각했다. set으로 구간을 관리하는 종류의 코딩은 굉장히 많이 쓰이지만 언제나 오류를 수반하고 참 힘든 코딩인 것 같다. 많이 연습해서 쉽게 할 수 있도록 해야겠다.