상위 99.99%의 PS

https://www.acmicpc.net/problem/5821 5821번: 쌀 창고 첫째 줄에 R, L, B가 주어진다. 둘째 줄부터 R개 줄에는 X[i]가 주어진다. (1 ≤ R ≤ 100,000, 1 ≤ L ≤ 1,000,000,000, 0 ≤ B ≤ 2,000,000,000,000,000) www.acmicpc.net - 이분 탐색 - 누적 합 논의 개수가 홀수일 때, 가운데에 있는 논에 창고를 세울 때 최소비용이 된다. 논의 개수가 짝수일 때는, 가운데 두 논의 좌표 a, b에 대해 a

www.acmicpc.net/problem/1396 1396번: 크루스칼의 공 첫째 줄에는 그래프의 정점의 개수 n과 간선의 개수 m이 주어진다. 그리고 두 번째 줄에서 m+1번째 줄까지는 a b c의 형태로 a와 b를 잇는 간선의 고유값이 c라는 의미이다. m+2번째 줄에는 알고 싶은 www.acmicpc.net 원래는 lca 공부하면서 풀려고 했는데, 누군가가 나보고 병렬 이분탐색 문제를 주면서 풀라고 하길래 이론만 강의로 듣고 다음날 까먹었다! 병렬 이분탐색에 대해서는 여기에 정말로 잘 나와있으니 모른다면 정독하고 오자. 열심히 구현했는데, 아직 완전히 내것이 된게 아니라 나중에 다시 한번 또 풀거다 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 2..

www.acmicpc.net/problem/1994 1994번: 등차수열 N(1≤N≤2,000)개의 음 아닌 정수들이 있다. 이들 중 몇 개의 정수를 선택하여 나열하면 등차수열을 만들 수 있다. 예를 들어 4, 3, 1, 5, 7이 있을 때 1, 3, 5, 7을 선택하여 나열하면 등차수열이 된다. www.acmicpc.net 정렬 후 이분 탐색 이런거도 dp라고 보는지는 모르겠다.. dp로 푼거는 아닌듯 시간복잡도 \(O(N^2 logN)\) [Python] 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 import sys input = sys.st..

www.acmicpc.net/problem/1321 1321번: 군인 첫째 줄에 부대의 개수 N(1 ≤ N ≤ 500,000)이 주어지고, 이어서 각 부대의 군사 수를 나타내는 정수가 N개 주어진다. 각 부대의 군사 수는 1000보다 작거나 같은 자연수이다. 그 다음 줄에 명령의 개 www.acmicpc.net 세그트리 기초문제?이다. 1~K번째 부대 인원의 수의 총합을 A_k라고 할때, x번 군인의 위치는 \(A_{k-1} \lt x \le A_k\) 를 만족하는 가장 작은 k가 되고, 이는 이분 탐색으로 빠르게 구할 수 있다. -소스코드 더보기 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 3..