전체 글 (28) 썸네일형 리스트형 Codeforces Round #591 (Div. 1) https://codeforces.com/contest/1240/ https://codeforces.com/blog/entry/70358 (Editorial) 나는 낮에 버츄얼만 돌렸다. 본 대회는 DDOS 공격으로 인해 unrated 됐다. 나는 대부분의 사람들과 마찬가지로 ABCD를 풀었는데, 푸는데 시간이 오래 걸린 편이었다. A. Save the Nature $N$개의 티켓이 있다. $i$번 티켓은 $p_i$의 가격을 갖는다. $a$의 배수번째에 팔린 티켓 가격의 $x\%$와 $b$의 배수번째에 팔린 티켓 가격의 $y\%$은 환경운동을 위해 쓰일 것이다. 티켓들의 순서를 잘 정하여, 최소 개수의 티켓을 팔아서 $k$이상의 돈을 환경운동에 쓰고 싶다. 팔아야하는 티켓 개수의 최솟값은? $x>y$라 .. 양수 가중치를 가지는 그래프에서 O(V+cE)로 최단경로 구하기 가중치가 없는, 혹은 모든 간선의 가중치가 1인 그래프에서는 BFS를 이용하면 $O(V+E)$로 최단경로를 구할 수 있다. 이를 응용하여, 가중치가 $c$ 이하의 자연수인 그래프에서 최단경로를 구하자. 가중치 $c$의 간선을, 가중치 $1$의 간선 $c$개로 나누자. 그러면 새로운 노드가 $c-1$개가 생길 것이다. 그러고 나면 간선이 $O(cE)$개, 정점이 $O(V+cE)$개인 그래프가 된다. 여기서 BFS를 통해 최단경로를 구하면 $O(V+cE)$로 최단경로를 구할 수 있다. 이 방법은 $c$가 작을 때 유용하다. https://www.geeksforgeeks.org/shortest-path-weighted-graph-weight-edge-1-2/ 참고. 내 코드 #include using name.. 0-1 BFS 가중치가 없는, 또는 모든 간선의 가중치가 1인 그래프를 생각하자. 그러한 그래프에서 한 점으로부터의 최단거리는 BFS로 구할 수 있다. 이것을 응용해서 간선의 가중치가 0 또는 1인 그래프에서 거리를 구해보자. (가중치가 0 또는 x인 경우에도 풀 수 있다.) 가중치 0의 간선으로 이어진 정점들은 모두 거리가 같다. 따라서 가중치 0의 간선을 만나면 연결된 정점들을 모두 같은 거리로 설정해주면 된다. BFS에 이를 적용하기 위해서는 queue가 아니라 deque를 이용하면 된다. 가중치 0의 간선은 먼저 처리해야 하므로 deque의 앞에 넣으면 된다. https://codeforces.com/blog/entry/22276 참고. 0-1 BFS를 이용하면 아래 문제들을 풀 수 있다. https://www.. CERC 2013 Escape, JOISC 2017 Sparklers CERC 2013의 Escape(https://www.acmicpc.net/problem/9539)와 JOISC 2017의 Sparklers(https://oj.uz/problem/view/JOI17_sparklers)를 풀어보자. Escape는 다음과 같은 문제를 풀어야 한다. 트리의 1번 정점에서 시작하여 간선을 따라 움직인다. 처음 체력은 0이다. 각 정점 $i$을 처음으로 방문하면 $H_i$만큼 체력을 얻는다. $H_i0)$의 부모 노드 $u$를 생각하자. $u$의 자식은 $v$만 있다고 생각하자. $H_u0$) 1. 리프 노드: $H_i0$이면 $c_i=0, h_i=H_i$ 2. 여러 자식 체인 합치기 : 이 체인들에서 가능한 많은 체력을 얻어가고 싶다. 따라서 현재 hp $\leq c_i$이면.. 이분 매칭 (Bipartite Matching) 이분 매칭은 이분그래프에서의 매칭을 의미한다. HopcroftKarp 알고리즘을 이용하면 $O(E\sqrt{V})$에 풀 수 있지만, 여기서는 더 쉬운 알고리즘만을 다루겠다. DFS를 활용하면 $O(VE)$로 최대 이분 매칭을 구할 수 있다. 참고. - 일반 그래프에서의 매칭은 더 어려운 문제이다. blossom 알고리즘을 이용하면 $O(V^2E)$에 된다고 한다. - weighted bipartite matching은 MCMF를 활용하여 풀 수 있다. DFS를 사용한 알고리즘은 상당히 간단하다. 이분 그래프를 $G=(L, R, E)$라 하자. $L, R$은 정점의 집합이다. $L$에 속한 정점을 차례대로 보면서 매칭을 추가해줄 것이다. $v \in L$에 대해 $v$와 연결된 정점 $u \in R$을 .. Persistent Segment Tree (PST) $x, y$좌표가 $0$ 이상 $N$ 미만의 정수인 점 $N$개가 있다. $x, y$좌표는 모두 다르다. 이 때, 특정 직사각형 내부에 있는 점의 개수를 묻는 쿼리가 들어온다. offline 풀이를 생각해보자. 직사각형 내부의 점의 개수를 구하는 쿼리는, $\sqsupset$ 형태의 구역에 있는 점들의 개수를 구하는 쿼리 2개로 쪼갤 수 있다. $\sqsupset$ 내부의 점의 개수를 구하는 쿼리들을을 $x$ 좌표($\sqsupset$에서 오른쪽 |) 순으로 정렬하고, 그 $x$ 좌표까지의 점들에 대해 $y$ 좌표를 BIT 또는 segment tree로 관리하면 $O(NlogN+QlogN)$에 해결할 수 있다. 이제 online 풀이를 생각해보자. offline과 같이 풀려고 하면 $O(N)$ 크기의 s.. Heavy-Light Decomposition (HLD) RMQ와 같이, 수열에서 풀 수 있는 문제들을 트리에서 풀어보자. segment tree를 이용하여 풀 수 있는 문제를 주로 다룬다. 트리를 체인 여러개로 쪼개고, 각 체인에서는 수열에서와 같이 segment tree를 이용해 답을 구한다. 그 후 여러 체인을 합쳐줄 것이다. 그러면 (원하는 구간이 걸쳐져있는 체인의 수) * (체인 1개에 대해서 구간 쿼리를 할 때 필요한 연산 수) 만큼의 연산이 필요하다. 따라서 트리에서의 구간이 적은 체인에 걸쳐지도록 하자. 이렇게 체인을 쪼개어 문제를 푸는 것이 HLD이다. HLD에서는 간선이 두 가지가 있다: Heavy edge, Light edge. Heavy edge들만 남겨놓고 Light edge를 지우면 체인들만 남게 되고, 이 체인들은 모두 조상-자식을 .. Centroid Decomposition 트리에서 분할정복을 해보자. 그러기 위해서는 트리의 중앙을 찾은 후, 그 중앙을 기준으로 나누어진 부분들의 크기가 충분히 작도록 해야 한다. 이 '중앙'을 centroid라 한다. 구체적으로는, 트리에서 centroid를 제거하여 생기는 forest에서는 모든 트리의 크기가 원래 트리의 절반이하가 된다. 트리의 centroid는 1개 또는 2개이고, 2개일 경우에는 그 2개가 인접하다. 트리에서 centroid를 잡은 후, 그 centroid를 제거하자. 그 후 나누어진 서브트리들에서 다시 centroid를 잡자. 이 과정을 반복하면 분할정복이 가능하다. 또는 centroid를 잡은 과정을 나타내면 centroid tree가 된다. 자세한 내용은 https://koosaga.com/145 참고. 내 코드.. 특이하게 Union Find하는 문제들 Union Find는 그래프에서 간선이 차례대로 생겨날 때, 두 정점이 같은 component에 있는지 판별하는 쿼리를 $O(logN)$에 해결하는 알고리즘이다. 흔히 사용하는 방법으로는 경로 압축과 랭크 비교가 있다. 이러한 방법으로 Union Find를 하면 component를 깊이가 작은 트리 형태로 관리하게 된다. 그런데 component를 특이한 형태로 관리하면 다른 종류의 쿼리들을 풀 수 있게 된다. 2019 FunctionCup의 갈라파고스 여행(island) (https://oj.uz/problem/view/FXCUP4_island)을 풀어보자. 다음과 같은 쿼리를 해결해야 한다. 간선들에 0 ~ M-1의 번호가 붙여져있는 그래프가 있다. 정점 A[i]에서 정점 B[i]까지 이동할 때, 사.. SOS dp (Sum over Subsets) Sum over Subsets 라는 이름답게, 부분집합의 합을 구하는 알고리즘이다. 구체적으로는, $F[mask] = \sum \limits_{i\subseteq mask} A[i]$를 구한다. $0\leq mask < 2^N$일 때 $O(N2^N)$으로 동작한다. for(int i = 0; i < (1 디닉의 알고리즘 Dinic's Algorithm 대표적인 최대 유량 알고리즘이다. 정점의 개수를 $V$, 간선의 개수를 $E$, 최대 유량(답)을 $f$라 할 때, $O(fE)$ 또는 $O(V^2E)$에 동작한다. 간선의 유량이 모두 같을 경우(모두 0 또는 1), 신기하게도 $O(min(V^{2/3}E, V^{3/2}))$에 동작한다. 직접적인 flow문제는 별로 없고, 최댓값을 구하는 문제를 max flow로 환원할 수 있는 경우가 종종 있다. 혹은 최솟값을 구하는 문제를 min cut으로 환원하기도 한다. 아래 링크들을 보고 공부하였다. https://jason9319.tistory.com/150 https://koosaga.com/18 https://koosaga.com/133 내 코드 #include using namespace std; #d.. AGC 038 https://atcoder.jp/contests/agc038/tasks ABCDEF 6문제 중 ABD 3문제를 풀었다. 레이팅이 오르긴 했지만, C를 못 푼 것이 아쉽다. 정수론이라서 풀려는 시도조차 안 했는데, 쉬운 문제였다.... A. 01 Matrix 쉬운 문제였지만 나는 모르겠어서 B를 먼저 풀었다. 위 왼쪽의 A*B크기 직사각형과 아래 오른쪽의 (H-A)*(W-B)크기 직사각형은 0으로 채우고 나머지는 1로 채우면 된다. B. Sorting a Segment 주어진 수열에서, 길이 $K$의 구간을 선택해서 그 구간을 정렬한다. 이 연산을 1번만 시행하여 얻을 수 있는 결과를 구하는 문제다. 위치 $i$에 이 연산을 시행하면 $[i, i+K-1]$ 구간이 정렬된다고 하자. $i$에 연산을 시행한.. Codeforces Round #588 (Div. 1) https://codeforces.com/contest/1229 https://codeforces.com/blog/entry/70008 (Editorial) Dasha Code Championship 대회의 open contest이었다. A, B, C, D, E1, E2, F 중 A B C 세 문제 밖에 못 풀었는데도 레이팅이 오른 대회였다. 초반에 서버가 죽는 일이 벌어졌는데도 rated로 진행되었다. A. Marcin and Training Camp 다른 A번 문제들에 비하면 어려운 편이었다고 생각한다. $b_i$가 양수이기 때문에 가능한 많은 수를 넣는 것이 좋다. 따라서 $a_i$가 가장 큰 것부터 그리디하게 보면서, 답에 포함하는 것이 가능하다면 넣고, 그렇지 않다면 넘어가면 된다. B. Kam.. 이전 1 2 다음