구사과

출처는 http://www.cs.tau.ac.il/~zwick/grad-algo-09/short-path.pdf흔히 알려진 알고리즘은 벨만 포드를 사용한 $O(nm)$ 시간 알고리즘이다. 이 글에서는 $O((n + m)\sqrt n \log W)$ 알고리즘을 소개한다.그래프에 음수 사이클이 없다면 퍼텐셜 함수가 존재해서 $p(u) - p(v) + w(u, v) \geq 0$ 이 되게 만들어 줄 수 있음이 잘 알려져 있다. 그래서 결정 문제를음수 사이클을 찾거나퍼텐셜 함수를 찾거나로 정의할 수 있다. 퍼텐셜 함수를 찾을 수 있으면 거기서부터는 $O(m + n \log n)$ 에 최단 경로를 찾는 것이 쉽기 때문이다.만약 모든 간선의 가중치가 -1 이상 (즉 음수 간선은 무조건 가중치 -1) 일 때 문제를 ..

ABC 127 B. Algae주어진 점화식을 계산하면 됩니다. (답은 int32 범위도 넘어가지 않습니다.)PA 2024. Zelki$D[i]$ 를 (조건을 만족하는) 선물 상자 하나를 골랐고, 그 안의 사탕의 무게 합을 $m$ 으로 나눈 나머지가 $i$ 일 때, 가능한 가격 합 최소라고 정의합시다. 원래 문제와의 차이는, 원래 문제에서는 선물 상자를 여럿 고를 수 있다는 점입니다.$D[i]$ 는 동적 계획법을 사용하여 구할 수 있습니다. $DP[x][i]$ 를, 사탕의 색상이 $x$ 이하인 사탕들만 고려하여 무게 합 나머지가 $i$ 가 되게 하는 방법이라고 합시다. $DP[x-1][_]$ 테이블이 채워져 있으면, 색상이 $x$ 인 사탕의 모든 경우를 다 시도하면서 $DP[x][_]$ 테이블을 채울 수 ..

Splay tree 등의 BBST 구현을 여러번 시도해 보았지만 내가 대회에서 직접 짜면 버그가 너무 많아서 보통 피해왔었다. 얼마 전 QOJ를 읽다가 Weight-Balanced Tree라는 Persistent BBST의 굉장히 간단한 구현체를 찾아 이 블로그에 소개한다. 이 구현의 장점은:Rotate 연산을 사용하지 않는다.Rotate 연산은 유도하기 대단히 귀찮아서 보통 암기해야 하고 실수하기 쉽다.사실 이 구현도 Merge에서 암기해야 할 부분이 있는데 Rotate보단 쉬운 거 같다. 그리고 그 부분은 실수를 조금 해도 괜찮다.리프 노드만이 실제 원소에 대응된다. 리프 노드가 아니면 대응되는 원소는 없으며, 왼쪽 자식 / 오른쪽 자식을 모두 가진다. 일반적으로 우리가 사용하는 세그먼트 트리등과 동..