최근 카이스트 대회 기출 문제가 run.kaist.ac.kr/contest 에 전부 올라와 있습니다. 테스트 데이터나 풀이를 전부 공개하였으니 많은 관심 부탁드립니다! 맨 아래 과거 기출 문제 / Past Problemset 섹션에 모두 올라와 있습니다. KAIST Contest 2018. Fractions 편의상, $A = C = 1$ 이라고 가정합시다. 이렇게 될 경우 $x, y$의 상한만이 존재하고 하한은 존재하지 않습니다. 이 가정을 하더라도 문제를 여전히 해결할 수 있는데, 만약에 위 문제를 해결하는 함수 $f(B, D)$ 가 존재한다면, 우리가 출력해야 하는 답은 포함-배제의 원리를 사용하여 $f(B, D) - f(A-1, D) - f(B, C-1) + f(A-1, C-1)$ 로 계산할 수 있..
(2018.11.07: ICPC 대회 난이도에 별점을 매겼습니다. 사실 제일 중요한 건 난이도인거 같아서 마음에 좀 걸렸는데, 이렇게 하면 조금 더 가시성이 있지 않을까 싶네요.) 공부하기 싫어서, 제가 평소에 어떻게 연습하는 지에 대해서 간략히 글을 씁니다. 이 글은 연습 방법론, 예를 들어 하루에 몇 시간씩 하는지 / 풀이는 언제 보는지 / 뭐 먹고 사는지 (...) / Secret Tip이 있는지 (……) 에 대해서는 전혀 언급하지 않습니다. 저러한 내용에 과도하게 걱정하시는 분들이 참 많은데, 별로 안 좋은 습관이라고 딱 잘라 말하겠습니다. 보통 상위권이라고 저런 거에 대단한 철학이 있지는 않습니다. 개인 성격 따라 제각기 하는 방법이 다릅니다. 본인 성격에 맞는 방법을 찾기 위해서는 시행착오 말..
ACM-ICPC Seoul Preliminary 2018
pre Scoreboard 지끈..뭐라 뭐라 더 쓰고 싶으나, 내 블로그가 불편한 이야기를 쓰기에 적합한 장소는 아니라고 생각이 든다. Problems / Solution Sketch 이번에는 문제 난이도가 비슷한 문제들이 많아서, 사람들이 느끼는 난이도에 이견이 매우 클 수 있다고 생각했다. 마음 같으면 스코어보드 읽고 많이 푼 순서대로 정렬하고 싶으나, 스코어보드가 공개되지 않은 상황이라 그냥 블로그 주인장 마음대로 정렬한다. I. Registration B. Farm 양의 수 $i$를 1부터 $N-1$ 사이의 정수로 고정하면, 염소의 수는 $N - i$ 마리이다. 그러면 그들이 먹는 음식의 양도 계산할 수 있다. 음식의 양을 $w$ 로 가지는 양의 수의 개수를 세어 주고, 유일하면 그 수를 출력하면..
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점 차는 느낌이 다르다. 주최측은..
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]$ 가 주어진..
- Total
- Today
- Yesterday