JJaewon의 PS하는 블로그

Link https://www.acmicpc.net/problem/17635 APIO 2019 2번 Tag Union-find 오프라인 쿼리 평방 분할 Time Complexity $O(Q\times (\frac{M}{B}lgM+B^{2}lgB))$ $(B=BucketSize)$ 정점 $N(\le 50,000)$개, 간선 $M(\le 100,000)$개인 그래프가 주어진다. 1. $i$번 간선의 가중치를 $w$로 변경 2. 정점 $v$에서 가중치가 $w$ 이하인 간선들만 거쳐서 도달할 수 있는 정점의 개수를 출력 두가지 쿼리가 $Q(\le 100,000)$개 주어진다. 오프라인으로 처리해도 된다. 1번 쿼리가 없을 때는, 간선들을 가중치의 내림차순으로 보면서 컴포넌트의 크기를 세주기만 하면 된..

Link https://www.acmicpc.net/problem/21607 2021 SciCom Qualification Test 2E번 Tag Segment Tree Spare Table Time Complexity $O(Q(lgN+lgQ)+XlgX)$ $(X=100003)$ $f(x)=2x^2-1,g(x)=4x^3-3x$이고, 길이 N의 수열 $A$가 주어진다. $f,g$를 구간에 적용하는 쿼리와 $A_i$를 $100003$으로 나눈 나머지를 구하는 쿼리가 주어진다. 이러한 쿼리를 $Q$개 처리해야 한다. 일단 $f,g$가 곱셈으로만 이루어져 있으니 나머지를 구하는건 그냥 해주면 될거 같고, $f,g$를 어떻게 하느냐가 문제다. 근데 왜 하필 $f,g$를 저렇게 줬을까? 뭔가 특별한 성질이 있나?..

Link https://www.acmicpc.net/problem/16909 Tag 스택 Time Complexity $O(N)$ 수열 $A$가 주어지고, $A$의 모든 구간 $[s,e]$의 최댓값-최솟값의 총 합을 구하는 문제다. 최댓값의 총 합과 최솟값의 총 합을 각각 구하자. 각각의 $A_i$에 대해 $A_i$보다 왼쪽에 있으면서 $A_i$보다 큰 수 중 가장 오른쪽에 있는 수의 인덱스를 $s_i$, $A_i$보다 오른쪽에 있으면서 $A_i$보다 큰 수 중 가장 왼쪽에 있는 수의 인덱스를 $e_i$이라 하자. 그러면 구간 $[a,b]$ $(s_i\le a\le i\le b\le e_i)$ 의 최댓값이 $A_i$가 된다. 그러한 구간의 개수는 $(i-s_i)(e_i-i)+e_i-s_i+1$이다..

Link https://www.acmicpc.net/problem/14870 KOI 2017 고등부 4번 Tag dp Segment Tree Time Complexity $O(N^{2}lgN)$ $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..

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(Nl{g}^{2}N)$ 각 정점에 가중치가 있는 포화이진트리를 평면에 그려서 x, y축에 평행한 임의의 직사각형 내부 가중치의 합을 최대화해야한다. 금광 하위호환...? 그냥 완전탐색 하면 된다. 포화이진트리에 노드가 $N$개면 높이가 $lgN$이고, 이는 직사각형의 위아래가 될 수 있는 경우의 수가 $l{g}^{2}N$ 밖에 없음을 의미한다. 이 모든 후보에 대해 $O(N)$에 최대 연속합을 구해주면 된다. Code