구사과

2, 4, 5번 문제의 아이디어를 구상했다.시간 여행각 $i$ 에 대해 $j \le i, A_i - K \le A_j \le A_i$ 를 만족하는 최소 $j$ 를 찾아 그 합을 출력하는 문제이다. $j \le i$ 조건은 함정이다. 어차피 $i$ 가 조건을 만족하기 때문에 무조건 저 조건은 성립한다. 그러면 $A_j$ 값이 특정 구간에 있는 최소 $j$ 를 찾는 문제가 되고, 이는 sliding window minimum 문제이다. $O(N + maxA)$ 나 $O(N \log N)$ 에 해결할 수 있다.공장단순하게는 끝점 작은 순으로 구간을 처리하면서 기존에 넣은 구간과 겹치지 않는 구간을 추가해 주면 된다. 쿼리가 들어올 때, 쿼리로 추가된 구간을 끝점 작은 순으로 정렬하자. Merge sort를 하..

출처는 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][_]$ 테이블을 채울 수 ..