구사과

(2024.09.02 - Meetings의 풀이를 작성하여 첨부하였다.)(2018.09.22 - 원문 작성)IOI 2018 Day 2가 종료되었다. 한국 학생들의 최종 성적은 다음과 같다.노영훈, 100 / 37 / 49 / 100 / 51 / 36, Day2 13등, 종합 12등. 금메달.강태규, 100 / 25 / 49 / 100 / 69 / 19, Day2 11등, 종합 17등. 금메달.김세빈, 100 / 37 / 49 / 63 / 51 / 60, Day2 20등, 종합 18등. 금메달.윤교준, 100 / 5 / 49 / 86 / 51 / 4, Day2 38등, 종합 59등. 은메달.IOI Statistics를 보았을 때, 평균 성적과 만점자를 통틀어 봐도 최근 10년 대회 중에서 이보다 어려운 하..

(2018.9.9 : 모든 문제의 풀이를 작성하였다.)IOI 2018 Day 1 대회가 종료되었다.한국 학생들의 성적은 다음과 같다. Day 1 기준이고, Day 2 점수를 감안하지 않았음을 유념하라. 김세빈, 100 / 37 / 49, 21등 - 56등 노영훈, 100 / 37 / 49, 21등 - 56등 강태규, 100 / 25 / 49, 70등 윤교준, 100 / 5 / 49, 137등 - 144등 미국의 Benjamin Qi가 만점인 300점을 받아냄으로써 Day 1의 압도적인 1등을 차지하였다. 그 뒤를 3번 문제를 해결한 학생들이 대다수 차지하였다. 흥미로운 점은 3번 문제를 해결한 많은 학생들이 2번 문제에서 충분한 점수를 받지 못했다는 점이다. 51점과 31점 차는 느낌이 다르다. 주최측은..

Garey / Johnson의 1981년 논문 "Scheduling Unit-time tasks with Release time and Deadline" 를 읽고 내용을 정리해 보았다. Competitive Programming에서는 2017년 ICPC World Finals에서 한 명도 풀지 못했던 문제인 "Scenery"의 풀이로 유명한 논문이다. 이 글에서는 $O(n^2)$ 알고리즘까지만 정리했으며, $O(n\log n)$ 알고리즘은 하지 못했다. ㅠㅠ 이 문제의 $O(n^2)$ 알고리즘은 매우 아름답다. 혼자 생각하지 못하더라도 보고 배울 가치가 충분하니 일독을 권한다. 여담 : 예전에 breakun 님이 BOJ 슬랙에 질문했던 문제 중 하나이다. $N$개의 구간 $[S_i, T_i]$ 가 주어진..