Link https://www.acmicpc.net/problem/10060 ICPC 2014 WF K번 Tag Greedy Sparse Table Segment Tree Time Complexity $O((N+K)lgN)$ N개의 방이 원형으로 연결되어 있다. K개의 감시카메라가 있어서, 각 감시카메라는 일정한 범위의 방을 감시한다. 이때 모든 방을 감시하기 위해 필요한 최소 카메라 개수를 구해야 한다. 일단 원형은 짜증나니까, 2N 길이의 직선으로 펴놓고 시작하자. 어떤 카메라를 하나 골라 시작점으로 잡는다. 그 뒤로는 그리디하게 카메라의 오른쪽 끝점을 밀면서 원형으로 잇기 위해 필요한 카메라의 최소 개수를 구하자. 모든 카메라에 대해 시작점으로 시도해보면 답을 찾을 수 있다. 이때 Sparse Ta..
Codeforces Round #642 (Div. 3)에 부계정으로 참가했다. 저번 Div. 4를 제외하고 첫 올솔브다 ㅎㅎ. 사실 Div. 2 올솔은 능력 밖이기도 하고. A. Most Unstable Array $N=1$이면 0 $N=2$이면 M, 아니면 2M 이다. B. Two Arrays And Swaps A에서 제일 작은것과 B에서 제일 큰것 swap을 반복해주면 된다. 왜 $N \le 30$? C. Board Moves 가운데로 모으는게 최적임을 알 수 있다. $O(N)$ 에 해도 되고, 일반항도 있다 카더라. D. Constructing the Array {구간의 길이, 구간의 시작점} pair로 우선순위 큐를 관리하면 된다. 길이와 시작점의 대소 우선순위가 다름에 유의하자. E. K-per..
Link https://www.acmicpc.net/problem/5813 IOI 2012 Day2 1번 Tag 트리 Time Complexity $O(NlgN)$ / $O(N)$ 네모 셀들로 이루어진 무한한 이차원 격자에 N개의 블록들을 놓았다. 비어 있는 셀들과 비어있지 않은 셀들은 각각 오직 하나의 컴포넌트를 이룬다. 이때 모든 두 블록 쌍에 대한 최단거리의 합을 계산해야 한다. 비어있는 셀들과 비어있지 않은 셀들이 각각 하나의 컴포넌트를 이룬다는 말은, 구멍이 없다는 말이다. X좌표가 같은 인접한 블럭들의 토막을 노드로 보고, 간선으로 이어 그래프를 만들면 문제 조건에 의해 트리가 된다. 이 트리 상에서 모든 두 정점 쌍의 거리의 합은, 모든 두 블록 쌍에 대한 최단거리의 Y좌표 합과 같다. 트리..
Link https://www.acmicpc.net/problem/16074 GCPC 2018 M번 Tag PBS Time Complexity $O((N+Q)lgN)$ 가중치가 있는 $N \times M$ 그리드가 있고, $(x1, y1)$ 와 $(x2, y2)$ 를 잇는 경로의 가중치의 최댓값의 최솟값을 묻는 쿼리가 Q개 주어진다. 쿼리 하나를 이분탐색으로 처리한다고 생각해보면, '가중치가 $k$ 이하인 정점들만 가지고 $(x1, y1)$ 와 $(x2, y2)$ 를 연결할 수 있는가?' 가 결정문제가 되고, 이는 Union-Find 를 이용해주면 된다. Q개의 쿼리를 처리하려면, 가중치가 작은 정점부터 보면서 추가하고 해당 mid값을 가진 쿼리에 대해 답해주면 된다. PBS 연습문제. Code
Link https://www.acmicpc.net/problem/18251 Good Bye, BOJ 2019! E번 Tag 완전탐색 Time Complexity $O(Nlg^{2}N)$ 각 정점에 가중치가 있는 포화이진트리를 평면에 그려서 x, y축에 평행한 임의의 직사각형 내부 가중치의 합을 최대화해야한다. 금광 하위호환...? 그냥 완전탐색 하면 된다. 포화이진트리에 노드가 $N$개면 높이가 $lgN$이고, 이는 직사각형의 위아래가 될 수 있는 경우의 수가 $lg^{2}N$ 밖에 없음을 의미한다. 이 모든 후보에 대해 $O(N)$에 최대 연속합을 구해주면 된다. Code
4.2 ~ 4.11 동안 푼 문제 정리 산만한 고양이 https://www.acmicpc.net/problem/14866 DFS 스패닝 트리를 만들고 Tree DP 느낌으로 서브트리 내부의 Back Edge들을 잘 카운트하고 케이스 분류하면 각 정점의 자식들을 확인하면서 사이클을 제거할 수 있는지 판단 가능하다. The Bridege on the River Kawaii https://www.acmicpc.net/problem/16695 처음 보면 좀 무서운데, $V
Link https://www.acmicpc.net/problem/10129 POI 2013/2014 Stage 2 3번 Tag dp Time Complexity $O(QN)$ $N$개 나무의 높이가 주어지고, $Q$마리의 새가 1번 나무에서 N번 나무까지 날아간다. 각 새는 한번에 $k_{i}$ 그루의 나무만큼 날아갈 수 있고, 현재 위치한 나무보다 높이가 같거나 높은 나무로 날아갈때 피로감을 느낀다. 각 새의 피로감 느끼는 횟수를 최소화해야한다. 쿼리가 있긴 한데 $Q \le 25$이라 그냥 따로따로 풀어도 상관없다. dp 점화식은 쉽게 나온다. $dp[i]=min(dp[j]+C)$ $(i-k \le j < i)$ ($C$는 $h[j] \le h[i]$일때 1, 아니면 0) 모든 j에 대해 고려하면 ..