구사과

https://beta.atcoder.jp/contests/arc103/tasks/arc103_d일단 일반성을 잃지 않고 $D_1 1$ 번 노드의 부모는 $i$번 보다 작은 번호를 가진다. 이 부분의 증명은 생략한다. Centroid의 성질을 생각해 보면 그렇게 어렵지 않다.고로 루트 (centroid) 를 기준으로 하나 하나 노드를 붙여나가는 식의 풀이가 될 것이라고 생각할 수 있으나, 생각처럼 잘 안된다. 어떠한 노드를 추가할 때 무슨 노드를 부모로 삼을 지가 명확하지 않다.여기서 발상을 전환시켜서, 위 과정을 반대 방향으로 해 보자. $N$번..

(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점 차는 느낌이 다르다. 주최측은..