구사과

(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]$ 가 주어진..

이전에 Off-line dynamic connectivity에서 썼던 내용의 연장선으로, Dynamic MST 문제를 오프라인으로 푸는 알고리즘에 대한 글을 써 보았다.