Problem Solving102 Heavy Light Decomposition N개의 정점을 가진 트리가 있다고 하자. 이 때 임의의 두 정점에 대해 이들을 잇는 경로는 O(N)개의 간선을 가진다. Heavy light decomposition(HLD)은 트리의 간선들을 적절히 일자 경로인 “묶음”들로 잘라, 임의의 두 간선 사이 경로를 O(lg N)개의 묶음으로 표현할 수 있게 해 준다. 이것을 세그먼트 트리 등의 일차원 자료 구조와 결합함으로써, 임의의 두 정점 사이의 경로에 대한 연산을 O(lg2N)에 할 수 있다. 간선들을 묶음으로 잘 나누는 방법은 다음과 같다. 1. 임의의 정점을 루트(R)로 지정하여, DFS 탐색을 한다. DFS 탐색을 하면서 각 정점에 대해 다음의 2가지를 계산한다. 1) 루트 노드와의 거리 2) 해당 정점이 루트 노드인 subtree의 크기 2. R.. 2018. 2. 15. 2015 ACM-ICPC Asia Phuket Regional Contest 5시간 대회인데, 창수랑 둘이 개인전으로 인터넷 예선처럼 3시간 동안만 했다. 2017. 9. 17. 2015 ACM-ICPC Asia Taiwan Online Programming Contest 2017. 9. 17. 2016 ACM-ICPC Asia Taiwan Online Programming Contest 창수랑 둘이서만 했는데, E번을 못 푼 걸 제외하면 썩 나쁘진 않은 듯.시간이 부족해서 G번과 I번은 문제도 못 읽었다.C번과 D번은 문제를 제대로 읽지 않아서 약간 시간이 소비되었다.한국 인터넷 예선과 비슷한 난이도이지만, 문제 수는 더 적은 세트라는 느낌이 들었다. 2017. 9. 16. AtCoder Regular Contest 074 C - Chocolate Bar간단한 수식으로 나올 것 같았는데, 예외적인 경우를 생각하기 귀찮아서 삼분검색 돌렸다.원래의 경우에서 상하좌우 바꾸고, 90도 돌리는 것만 고려해주면 되어서 실제 작성한 코드는 짧다.소스코드 D - 3N Numbers왼쪽에서부터 어느 곳까지 N개를 고르고, 그 이후 구간에는 N개를 고르는 것으로 볼 수 있다.따라서 전처리로 왼쪽에서 어디까지 N개를 골랐을 때의 최댓값, 오른쪽에서 어디까지 N개를 골랐을 때의 최솟값을 구해놓으면 답을 쉽게 계산할 수 있다.소스코드 E - RGB Sequence문제를 안 읽어봤다. F - Lotus Leaves플로우 네트워크를 만들고, 정점을 이분화 한다.시작점과 도착의 경우, 이분화한 정점 사이의 용량을 무한대로 준다.이 외의 정점들은 이분화.. 2017. 5. 21. 이전 1 2 3 4 5 6 ··· 21 다음
