국민대학교에서 알고리즘 대회가 있었다. 왠만하면 본선은 붙지 않을까 + 붙으면 서울 구경이나 해야지 하는 생각으로 예선을 신청했는데... 예선 예선은 온라인으로 한시간동안 진행했다. 캠 켜고 핸드폰 켜고 귀찮았다. 1번은 어디서 많이 본 문제였다. https://codeup.kr/problem.php?id=3095 걍 뚝딱 풀었다. 4분? 2번은 사다리타기를 시뮬레이션 하는 문제였다. 간선이 10만개였나? 간선을 단방향으로 분리해서 생각해보면 어차피 한번씩밖에 안지나간다. 그래서 대충 lower_bound 같은거 때려가면서 $O(lgN)$에 간선 따라가는 풀이를 구상했다. 어... 근데 구현이 어렵더라. 한시간 내내 디버깅하다 결국 제출 한번 못해보고 시간이 끝났다. 문제는 둘 다 쉬웠다. 근데 내가 개..
Link https://www.acmicpc.net/problem/14870 KOI 2017 고등부 4번 Tag dp Segment Tree Time Complexity $O(N^2lgN)$ $N \times N$ 격자에 조개가 있다. 각 점에서 $(1,1)$로 최단거리로 이동하면서 조개를 주울 수 있는 최댓값을 구해야 한다. 한번만 구하는게 아니라, $N$개의 쿼리가 주어져서 한 지점의 조개 개수가 1 증가하거나 감소한다. 이때 모든 지역에서 주울 수 있는 조개 개수의 최댓값의 합을 출력해야 한다. 먼저 $(1,1)$로 이동하는것을 $(1,1)$ 에서 각 지점으로 이동하는 것으로 바꾸어 생각하자. 그러고 나면 쿼리가 없는경우 아주 간단한 dp로 풀리는 것을 알 수 있다. 이제 쿼리를 어떻게 처리하느냐가..
Link https://www.acmicpc.net/problem/16027 CEOI 2018 2번 Tag dp Segment Tree Time Complexity $O(NlgN)$ 수열과 정수 X가 주어진다. 수열의 연속된 구간의 수에 -X ~ X 만큼 더하는 연산을 단 한번 해서, 이 수열의 LIS 길이를 최대화해야한다. 구간 [l. r]에 k를 빼는게 최적이라고 하자. 그럼 구간 [1, r]에 k를 빼도 결과는 같다. 그럼 구간 [r+1, N]에 k를 더해도 결과는 같다. k가 아니라 X를 더해도 결과는 같다. 따라서 모든 i에 대해 구간 [i,N]에 X만큼 더하면서 최대를 찾으면 된다. dp1[i]: i번째 수를 마지막으로 하는 최대 LIS 길이. dp2[i]: i번째 수를 시작으로 하는 최대 L..
Link https://www.acmicpc.net/problem/17101 Tag Sparse Table Segment Tree Euler Tour Technique Time Complexity $O(NlgN)$ N개의 정점으로 이루어진 트리가 주어지고, 1부터 N까지의 k에 대해, 1번 정점부터 k번 정점까지만 사용한 트리의 센트로이드를 출력해야 한다. 정점이 하나 추가되면 센트로이드는 최대 1칸 이동한다. 그 방향은 정점이 새로 추가된 쪽일 것이다. 증명은 안해봤는데, 직관적이고 짜니까 맞더라. 1번 정점을 루트로 잡자. 새로 추가된 정점이 현재 센트로이드를 루트로 하는 서브트리 안에 있다면, 다음 센트로이드의 후보는 새로 추가된 정점에서 (거리-1) 만큼 위로 이동한 점일 것이다. 서브트리 안에 ..
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)
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