알고리즘 공부방

문제 oj.uz/problem/view/JOI18_construction 문제 보기 - Construction of Highway (JOI18_construction) :: oj.uz 문제 보기 - Construction of Highway (JOI18_construction) oj.uz 트리가 주어지고, 처음에는 1번 노드밖에 없다. 한번의 업데이트 때마다, 지금 존재하는 트리에 하나의 간선을 추가하여 새로운 노드를 붙이는데, 이 때 루트에서부터 새로 붙인 노드까지의 경로의 정점들의 가중치를 일렬로 나열했을 때 만들어지는 수열의 inversion을 출력해야 한다. 또한, 업데이트 이후, 루트에서부터 새로 붙인 노드까지의 경로의 모든 정점들의 가중치는 모두 새로 붙인 정점의 가중치로 바뀌게 된다. $N

문제 oj.uz/problem/view/JOI19_mergers 문제 보기 - Mergers (JOI19_mergers) :: oj.uz 문제 보기 - Mergers (JOI19_mergers) oj.uz 트리 상의 각 노드는 특정한 색으로 칠해져 있을 때, 트리가 "분할 가능하다"는 것은 트리를 연결된 두 개의 컴포넌트로 쪼개서, 모든 색이 정확히 하나의 컴포넌트에만 속하게 할 수 있다는 것이다. 서로 다른 두 색을 합칠 수 있을 때, 합치는 연산의 횟수를 최소로 해서 트리가 분할 가능하지 않도록 해야 한다. $Ndep[v]) swap(u, v); for(int i=20; i>=0; i--) if(dep[par[v][i]]>=dep[u]) v=par[v][i]; if(u==v) return u; for..

문제 https://oj.uz/problem/view/JOI19_ho_t5 문제 보기 - Unique Cities (JOI19_ho_t5) :: oj.uz 문제 보기 - Unique Cities (JOI19_ho_t5) oj.uz 트리가 주어지고, 각 정점에 색이 칠해져 있을 때, 정점 $x$에 대한 unique한 정점 $y$를 다음과 같이 정의한다. $x$와 $y$의 거리가 $d$일 때 $x$에서 거리가 $d$인 $y$가 아닌 다른 정점 $z$가 존재하지 않는다. 각 정점에 대해, unique한 정점들의 서로 다른 색들의 개수를 구해야 한다. $M=dep-H[now]) cnt[V.back().second]--, V.pop_back(); if(chk[now]) ans[now]=V.size(); } els..

문제 https://oj.uz/problem/view/IOI19_split 문제 보기 - Split the Attractions (IOI19_split) :: oj.uz 문제 보기 - Split the Attractions (IOI19_split) oj.uz 연결된 무방향 그래프가 하나 주어졌을 때 정점들을 $A$, $B$, $C$ 세 개의 집합으로 분리해야 한다. 조건은 $A$, $B$, $C$의 각 집합의 크기는 이미 정해져 있고, 세 집합들 중 적어도 두개는 하나의 커넥티드 컴포넌트를 이루어야 한다. ($N

https://oj.uz/problems/source/20 1. garden 첫 번째로, 각 정점마다 상태가 2가지가 있다.1. 최솟값 간선으로 갈 수 있다. ( 이 간선을 전에 안 지남 )2. 최솟값 간선으로 갈 수 없어서 두번째 최솟값 간선으로 간다. ( 최솟값 간선을 이미 지남 ) 따라서 노드들의 상태를 위의 1, 2번 상태 2개로 나누어 만들자.0~N-1 : 1번 노드 / N~2N-2 : 2번 노드 이제 각 노드들에서 다른 노드로 상태가 유일하게 정해지니, outdegree = 1인 그래프라고 생각할 수 있고, 이를 통해 Functional Graph 라는 것을 알 수 있다. 이제 마지막으로 원래 문제로 돌아가서 어떤 정점 P로부터 K번 간선을 지나고 얻을 수 있는 경로를 구해주면 된다. 일단 o..

https://www.quora.com/q/threadsiiithyderabad/Centroid-Decomposition-of-a-Tree Centroid Decomposition 은 트리에서 분할정복을 할 수 있도록 해주는 방법이다. 분할정복은 다음과 같이 생각해볼 수 있다. 어떤 구간 [l, r]을 잡아도 어떠한 가운데 점 k를 잡아서 [l, k], [k+1, r] 로 쪼갤 수 있다. 또한, 분할정복에서 나오는 k들에서 [a, k] 와 같은 구간의 개수는 $O(NlogN)$ 개이다. 단순히 말해, 모든 구간들을 $O(NlogN)$ 개의 구간 2개의 합으로 나타낼 수 있으니 이 $NlogN$ 개를 관리하여 해결한다는 것이다. 트리에서도 Centroid 라는 점은 그 점을 제거하면 나오는 서브트리의 집합..

Heavy Light Decomposition 은 트리에서 segment tree 등의 자료 구조를 활용할 수 있도록 만드는 방법이다. 1차원에서 업데이트, 쿼리를 처리하는 문제는 segment tree 등의 자료구조를 활용하여 풀 수 있다. 하지만 트리에서는 이 과정이 어렵기 때문에 트리를 몇개의 체인으로 쪼갠 후 각 체인에서 segment tree 등을 사용하는 것이다. 하지만 만약 이 체인의 수가 많아지면 그만큼 시간이 많이 걸리기 때문에 체인의 개수를 적당히 적게 만드는 방법이 필요하다. HLD 는 다음과 같이 트리에서 각 노드에서 자식들 중 가장 서브트리가 큰 서브트리까지의 간선을 "무거운 간선"으로 분류한다.이렇게 해서 "무거운 간선"들로만 묶이면 체인들 몇개로 트리가 분해되게 된다. 이때 가..

문제 https://codeforces.com/contest/1187/problem/E 트리에서 어떤 노드를 시작으로 선택한 노드들과 인접한 노드들을 골라 검정색으로 칠하는 과정을 계속 반복한다. 이때 노드 하나를 선택할 때 아직 색칠되지 않은 컴포넌트의 크기만큼의 점수를 얻을 때, 점수의 최댓값을 구하는 문제이다. 풀이 가장 먼저, 처음에 선택하는 노드를 하나 정해놓고 생각해보자. 다음에 선택하는 노드는 그 노드와 연결되어 있는 점이어야 하고, 다음에 선택할 점들을 어떤 순서로 골라도 상관이 없다. 이를 이용하면, 다음을 알 수 있다. 루트 하나를 고정시켜 놓은 트리에서, 각 노드마다 서브트리의 크기를 구하면 그 서브트리 크기의 합이 바로 답이 된다. 이는 트리 DP를 이용하여 구할 수 있다. dp[v..