구사과

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

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

5월 22일 KAIST RUN에서 봄 대회를 진행하였다. 대회는 백준 온라인 저지에서 진행하였으나 Open Contest의 경우 Codeforces Gym에서도 진행하였다.아래는 본 대회의 Scoreboard이다.ProblemsOpen Contest ScoreboardCodeforces Gym ArticleEditorialTests & Checker & Solutions

수학적 귀납법 글의 20번 문제 풀이를 적어보았다. 삼성전자 소프트웨어 멤버쉽 과제의 일환으로 써서 글이 많이 길다. 고로 PDF로 따로 첨부한다.

1. POI디스크립션을 차근차근 읽으면서, 문제의 점수, 참가자의 점수, 참가자의 등수를 문제에 적혀있는 그대로 계산하면 됩니다. 2. 내일 할 거야문제를 쉽게 변형해서, 과제 리스트가 주어졌을 때 모든 과제를 마칠 수 있는지를 yes / no로 판별하는 문제를 생각해 봅시다. 이 경우 과제를 데드라인 순으로 정렬한 후 처리하는 그리디 알고리즘이 최선임을 증명할 수 있습니다. (데드라인이 큰 것을, 데드라인이 작은 것보다 먼저 처리할 이유가 없음) 한편, T일 쉰다는 것은, 사실 모든 데드라인을 T일 앞당긴 후 과제를 시작한다는 것과 동치입니다. 고로 과제를 하는 순서가 바뀌지 않습니다. 실제 T를 구하는 것은 과제를 역순으로 보면서 할 수 있습니다. 3. Archery Tournament원은 빠르게 다..

(2017.10.01 초판)(2018.01.27 문제집 추가)내가 만든 문제집을 내가 찾기 힘들어서, 정리하고자 만들었다. 이렇게 돌아보니까 근본 없다.. 전부 소개하기는 아까우니까, 별점 붙여서 별점 높은 것만 소개. convex hull trick https://www.acmicpc.net/workbook/view/476 (★★★★)컨벡스 헐 트릭 연습 문제집. 난이도는 쉽지 않다.FFT https://www.acmicpc.net/workbook/view/824 (★★★★★)FFT 연습 문제집. 이것도 쉽지 않다. FFT 쓰는 문제를 거의 전부 모은 것 같다.Segtrees are too mainstream https://www.acmicpc.net/workbook/view/912 (★★★★☆)Spl..