구사과

이집트 알렉산드리아에서 IOI 2024 Day 1 대회가 진행되었다. Day 1 기준 한국 학생들의 성적은 다음과 같다.김은성, 100 / 58.64 / 59, 217.64점, 22등정희우, 100 / 53.89 / 59, 212.89점, 26등정민찬, 100 / 79.64 / 17, 196.64점, 43등우민규, 100 / 31.40 / 59, 190.40점, 52등올해도 작년과 같이 모든 학생들의 성적이 금메달 / 은메달의 경계선에서 멀지 않다. 또한 그 경계선의 점수 차가 크지 않은 편이다. Day 2의 결과가 매우 중요할 것으로 보인다. 한국 학생들은 매년 Day 2 결과가 더 좋은 편이다. Day 2에서 좋은 결과를 내기를 소망한다.Day 1의 만점자는 중국의 Kangyang Zhou로 대회 시..

IOI 2018 Day 2 풀이를 작성할 당시 Meetings 문제를 해결하지 못해서, "36점 초과의 풀이는 작성 중입니다" 라고 하고 풀이를 비워두었다. IOI 2024 참관을 위해 알렉산드리아로 가는 비행기에서 드디어 100점 풀이 작성을 완성했다. 원래 글을 끌어올리기에는 시간순 정렬을 너무 깨는 것 같아서 개별 글에 작성한다.Problem길이 $N$의 양의 정수 배열 $A_0, A_1, \cdots A_{N-1}$ 이 있다. $0 \leq L \leq v \leq R $Cost(L, R, v) = \sum_{i = L}^{v-1}{(Max_{j=i}^{v}(A_j))} + \sum_{i = v}^{R}{(Max_{j=v}^{i}(A_j))}$$Q$ 개의 질의가 주어진다. 질의로 $L, R$이 주..

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를 하..