알고리즘 공부방

https://apio2019.ru/https://oj.uz/problems/source/389https://koosaga.com/232 내가 참가한 첫번째 apio 대회이다. 대회 결과는... 30점으로 매우 참혹한 점수가 나왔다.나는 대회시간에 device 를 읽고 어려운 수학문제라 판단하여 기본적인 부분점수만 긁고 풀지 않았는데, 이것이 가장 쉬운 문제였다. 대신 나는 마지막 문제였던 lamps에 모든 시간을 쏟아부었고, 결국 완벽한 풀이를 찾은 후 2D segment tree 구현, 경로압축까지 구현을 끝냈는데 MLE가 나서 결국 이것도 섭태밖에 긁지 못했다. 나중에 다시 풀어보니 경로압축 없이 fenwick + dynamic segment tree 하나만 있어도 AC가 나왔다...이번 년도의 문..

Li Chao Tree는 일차함수들의 볼록 껍질을 관리하는 자료 구조로, 기울기가 단조성을 보이지 않는 경우의 CHT 문제들을 해결하기 위하여 사용된다. https://cp-algorithms.com/geometry/convex_hull_trick.html 기본적인 꼴은 segment tree와 동일하다. 각 노드에는 그 노드의 구간을 담당하는 직선이 하나씩 있는데, 이때 주의할 점이 이 구간에서 이 직선이 항상 최대라는 것이 아니라 최댓값 후보 직선들 중 하나라는 것이다. 업데이트는 그 구간에 이미 들어 있던 직선과 지금 직선의 양 끝 부분의 함숫값을 비교한다. 만약 함숫값이 어느 하나가 양쪽 모두 크다면, 전체 구간에서 다 큰 것이기 때문에, 유지하던가, 갱신한다. 하지만 그것이 아니라면 원래 있던 ..

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 라는 점은 그 점을 제거하면 나오는 서브트리의 집합..

https://koosaga.com/121 https://codeforces.com/gym/100551/problem/A https://www.acmicpc.net/problem/16911 cp-algorithms.com/data_structures/deleting_in_log_n.html 1. 간선 추가 2. 간선 삭제 3. 정점 u, v가 연결되어 있는지 판별 이 문제를 online 으로 처리하는 것은 매우 어려운 문제이다. 따라서 Offline 으로 분할정복을 활용하여 해결하자. 가장 먼저, 각 간선의 생존시간을 시간축에 표시하면 어떠한 구간이 된다. 이 구간을 segment tree에 $logN$ 개의 노드에 업데이트 된 것이라고 생각하고, 이후 segment tree의 노드들을 전위순회하면서 u..

https://blog.myungwoo.kr/100 https://cubelover.tistory.com/14 PST는 N개의 세그먼트 트리를 만드는데, 전체 공간 복잡도가 $O(NlogN)$ 인 자료구조이다. 앞의 세그먼트 트리에서 하나의 값만 변화하는 새로운 세그먼트 트리를 만들기 위해서는 원래 세그먼트 트리의 대부분의 노드들을 재활용하고 새롭게 값이 바뀐 부분의 노드들만 변화시켜주면 된다. 이러한 이유로, 보통 2D 점 관리를 위한 자료구조로 Merge Sort Tree 와 함께 사용된다. 또한, Persistent 하게 구현되어, 수정이 불가능하다는 단점이 있다. struct Node { int val; Node *lc, *rc; Node() : val(0), lc(NULL), rc(NULL) {..

문제 https://www.acmicpc.net/problem/10556 10556번: KAMIONI The first line of input contains the integers N and M (1 ≤ N ≤ 105, 1 6 M 6 105), the number of trucks and the number of pairs of trucks we want to know the number of encounters for. The ith of the following N lines contains the description of the rout www.acmicpc.net 어떤 한 트럭이 수직선 상에서 A1, A2, A3, A4, ... , An (A1>A2A4 ... or A1A3

https://www.acmicpc.net/workbook/view/914 수열과 쿼리 1, 3 https://www.acmicpc.net/problem/13537 https://www.acmicpc.net/problem/13544 Merge Sort Tree를 이용하여 해결할 수 있다. 주어진 구간의 $logN$ 개의 노드들에 대하여 K 이상의 수들을 이분탐색하면 $O(NlogN+Qlog^2{N})$ 안에 해결할 수 있다. 수열과 쿼리 5 https://www.acmicpc.net/problem/13547 Mo's algorithm 으로 해결할 수 있다. 특정 구간에 오른쪽, 왼쪽에서 삽입, 삭제하는 시간이 O(T) 라 한다면 전체 시간복잡도는 $O(N^{1.5}T)$ 안에 해결할 수 있다. 서로 다른..

문제 https://www.acmicpc.net/problem/10355 10355번: Most Influential Pumpkin Pumpkins in Hagrid's garden have come to life! Now they walk, talk, date … and, of course, organize elections to choose the Head Pumpkin! It turns out that it is pretty simple to guess who will win the next elections - it will be one of the pumpkins of t www.acmicpc.net 처음에 입력 수열 A가 주어지고, 각 쿼리마다 [l, r]에 1씩 더하고, 전체 수열의 중앙값을..

http://apio-olympiad.org/2016/https://oj.uz/problems/source/184https://koosaga.com/113 3. Gap Subtask 1 한번에 양 끝의 값 2개씩 알아간다고 생각하자. 지금 아는 끝값으로 쿼리를 날리면 그 다음 끝값 2개를 알 수 있다. 사용하는 쿼리의 개수는 ceil(N/2) 개로, 30점을 받 수 있다. Subtask 2 Subtask 2에서는 쿼리의 개수만 중요한 것이 아니라, 한 쿼리가 적은 수들을 덮고 있어야 한다. 만점을 얻기 위해서는 한가지 중요한 관찰이 필요하다.일단 첫번째 쿼리로 최소값과 최대값 s, e를 구했다고 생각하자. [s, e] 구간 안에 gap들은 N-1개가 있으니, max gap < (e-s)/(N-1) 의 상..