구사과

1. POI디스크립션을 차근차근 읽으면서, 문제의 점수, 참가자의 점수, 참가자의 등수를 문제에 적혀있는 그대로 계산하면 됩니다. 2. 내일 할 거야문제를 쉽게 변형해서, 과제 리스트가 주어졌을 때 모든 과제를 마칠 수 있는지를 yes / no로 판별하는 문제를 생각해 봅시다. 이 경우 과제를 데드라인 순으로 정렬한 후 처리하는 그리디 알고리즘이 최선임을 증명할 수 있습니다. (데드라인이 큰 것을, 데드라인이 작은 것보다 먼저 처리할 이유가 없음) 한편, T일 쉰다는 것은, 사실 모든 데드라인을 T일 앞당긴 후 과제를 시작한다는 것과 동치입니다. 고로 과제를 하는 순서가 바뀌지 않습니다. 실제 T를 구하는 것은 과제를 역순으로 보면서 할 수 있습니다. 3. Archery Tournament원은 빠르게 다..

(2017.10.01 초판)(2018.01.27 문제집 추가)내가 만든 문제집을 내가 찾기 힘들어서, 정리하고자 만들었다. 이렇게 돌아보니까 근본 없다.. 전부 소개하기는 아까우니까, 별점 붙여서 별점 높은 것만 소개. convex hull trick https://www.acmicpc.net/workbook/view/476 (★★★★)컨벡스 헐 트릭 연습 문제집. 난이도는 쉽지 않다.FFT https://www.acmicpc.net/workbook/view/824 (★★★★★)FFT 연습 문제집. 이것도 쉽지 않다. FFT 쓰는 문제를 거의 전부 모은 것 같다.Segtrees are too mainstream https://www.acmicpc.net/workbook/view/912 (★★★★☆)Spl..

POI 2009/2010. Pilots$N$개의 수가 주어질 때, 연속 구간 중 (구간 내 최댓값) - (구간 내 최솟값) $\leq T$를 만족하는 최대 길이의 연속 구간을 찾는 문제이다. $N \leq 3000000$을 만족한다.데큐를 사용해서 Sliding window로 구간 최댓값 / 최솟값을 구하는 알고리즘이 잘 알려져 있다. 이 알고리즘에 inchworm을 적용하여서 문제를 해결할 수 있다. 처음에 [1, 1] 구간에서 시작하여. (최댓값) - (최솟값) $ \leq T$ 를 만족할 때까지 구간의 끝점을 늘린다. 더 이상 늘릴 수 없으면, 시작점을 늘리면서 계속한다. 이러한 식으로 구간의 길이를 최대화하면서 데큐를 관리해 주면 최대 구간의 길이를 알 수 있다. 고려대학교 2017 경시대회. L..