알고리즘 공부방

문제 oj.uz/problem/view/IOI20_plants 문제 보기 - 식물 비교 (IOI20_plants) :: oj.uz 문제 보기 - 식물 비교 (IOI20_plants) oj.uz 원 위에 0~N-1의 N개의 수가 배열되어 있는 순열 $A$가 있다. 이 때 $R_i$는 i번째 칸부터 오른쪽으로 연속한 $K-1$개의 수들 중 $A_i$보다 큰 수들의 개수로 정의된다. 수열 $R_i$와 쿼리 (x, y)가 Q개 주어질 때, 가능한 모든 $A_i$에서 $A_xA_y$를 만족하는지, 아니면 두 경우 모두 가능한지 판별해야 한다. 단, 주어지는 $R$는 대응되는 $A$가 적어도 하나 존재하는 수열로 주어진다. $K1; init(node*2, tl, mid); init(node*2+1, mid+1, t..

문제 oj.uz/problem/view/JOI19_dishes 문제 보기 - Two Dishes (JOI19_dishes) :: oj.uz 문제 보기 - Two Dishes (JOI19_dishes) oj.uz 두가지 요리가 있고, 각 요리를 완성하기 위해서는 각각 $N$, $M$개의 단계를 거쳐야 한다. 각 단계마다 수행하는 시간이 주어지고, 각 단계를 $A_i$ 시간 이하로 끝낸다면 $B_i$의 보상을 받을 수 있다. 각 요리의 단계들은 순서대로 시행해야 하며, 두 요리의 단계들을 번갈아 가며 하는 것은 허용된다. 이 때 얻을 수 있는 보상을 최대화해야 한다. $N=Y_i)$ 구간에 더해줌 원래 계단 꼴이었고, 뒤쪽 구간에 $P_i$를 더하는 과정에서 깨진 계단을 다시 맞춰주는 형식이니, 요약하자면 ..

문제 oj.uz/problem/view/JOI19_antennas 문제 보기 - Two Antennas (JOI19_antennas) :: oj.uz 문제 보기 - Two Antennas (JOI19_antennas) oj.uz N개의 안테나마다 $A$, $B$, $H$의 값이 주어지는데, 이는 $i$번째 안테나가 통신할 수 있는 거리의 범위가 $A$이상 $B$이하이며, 높이가 $H$라는 것을 의미한다. 서로 다른 두 안테나 $i, j$ 사이의 거리는 $|i-j|$로 정의된다. 이 때 Q개의 $(l, r)$쿼리가 주어지는데, 이는 $[l, r]$구간에 있는 안테나들 중 서로 양방향으로 통신할 수 있는 $i$와 $j$에 대하여 $|H_i-H_j|$의 값들 중 최댓값을 출력해야 한다. $N

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://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/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)$ 안에 해결할 수 있다. 서로 다른..