알고리즘 공부방

문제 oj.uz/problem/view/JOI19_cake3 문제 보기 - Cake 3 (JOI19_cake3) :: oj.uz 문제 보기 - Cake 3 (JOI19_cake3) oj.uz N개의 케이크 조각이 있고, 이중 M개를 뽑아 적당히 배열하여 $\sum_{i=1}^{M}V_i-\sum_{i=1}^{M}|C_i-C_{i+1}|$값을 최대화해야 한다. $M1; node->lc=new Node(); node->rc=new Node(); makeTree(node->lc, tl, mid); makeTree(node->rc, mid+1, tr); } Node *addTree(Node *node, int tl, int tr, int pos) { if(poscnt+1; ret->sum=node->sum+co..

문제 https://oj.uz/problem/view/JOI19_examination 문제 보기 - Examination (JOI19_examination) :: oj.uz 문제 보기 - Examination (JOI19_examination) oj.uz N개의 $(x, y)$점이 들어오고, Q개의 $(a, b, c)$쿼리가 들어온다. 쿼리의 의미는 $x>=a, y>=b, x+y>=c$를 만족하는 점들의 수를 세는 것이다. $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가 나왔다...이번 년도의 문..

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..

$N*M$ 크기의 격자에 다음과 같은 두 쿼리가 주어진다. 1. 한 칸의 값을 바꾼다 2. (x1, y1) ~ (x2, y2) 의 합, 최댓값, 최솟값 등을 구한다. 이 문제는 1차원의 문제가 segment tree 를 이용하면 풀리듯이 2D Segment Tree 를 이용하면 풀 수 있다. 하지만 2D Segment Tree 를 사용하면 공간 복잡도가 다이나믹 세그 + 메모리 제한이 빡빡할 경우에는 경로 압축까지 해 주어야 $O(NlogN)$ 이 나오기 때문에 시간, 공간의 측면에서 모두 비효율 적이다. 하지만 이 문제가 오프라인으로 풀 수 있다면 2D Segment Tree 를 구현하지 않아도 더 빠르게 풀 수 있다. 바로 분할 정복을 이용한 것이다. 시간의 흐름에 따라 1, 2번 종류의 쿼리가 하나..

문제 https://www.acmicpc.net/problem/1725 히스토그램에서 최대 넓이의 직사각형을 찾는 문제이다. 풀이 i부터 j까지 선택을 하면 \( (j-i+1)\times min({A[i], …, A[j]}) \) 가 넓이가 된다. (s, e)의 답을 구하기 위해서 (s, mid), (mid+1, e) 의 답은 재귀로 구하고, 왼쪽 부분문제와 오른쪽 부분문제에 걸쳐 있는 답만 구하자. 처음에는 mid, mid+1만 포함되어 있는 직사각형을 만들고, 좌우로 한칸씩 늘려가며 선택하며 답을 구한다. 답은 양 끝에서 더 큰 쪽으로 확장시켜 나가는 것이다. 물론 이 방법은 각 단계에서 최적의 선택을 해 나가는 그리디이다. 그리디 -> 증명 -> 귀류법 (!) 위 그림에서 그리디 알고리즘으로 선택한..