구사과

2018 2019는 전부 금 상위권으로 받았던 것 같은데 이번에는 은메달로 떨어져서 슬프다. C번은 아이디어를 찾는 것도 그다지 쉽지 않았는데, 구현에 있어서는 더 많은 문제가 있었다. 순탄치 않은 대회였던 것 같다. 올해 학생들 성적은 1금5은으로 예년과 비슷한 편으로 보인다. 반딧불이 300점 만점에 300점을 받아서, 2015년 이후 첫 APIO 만점과 함께 금메달을 얻었다. 반딧불 학생은 올해 IOI 국가대표이기도 한데, 아직 고등학교 1학년이니 앞으로도 좋은 결과가 기대된다. 그 뒤를 이어 이온조, 최서현, 장태환, 김지훈, 최은수 학생이 은메달을 얻었다. 모두 축하합니다! 내가 작성한 모든 코드는 이 링크에 있다. 1. 벽 칠하기 Subtask 1 (12점) 특정 벽을 칠할 수 있는 일꾼이 누..

유량(flow) 관련 알고리즘을 공부했다면 이분 그래프의 최대 매칭에 대해서는 익숙할 것이다. 이분 그래프에서 최대 매칭을 구하는 것은 크게 두 가지 의미에서 중요하다. 첫 번째는 문제 그 자체 에 대한 관심이다. 예를 들어, 택시 애플리케이션이 승객과 기사를 매칭하는 방법이나 결혼 중개업체가 남자와 여자를 짝짓는 방법 모두 이분 그래프의 매칭으로 표현할 수 있다. 두 번째는 이 문제가 다른 문제를 푸는데 어떻게 응용 될 수 있는지이다. 예를 들어, Konig's theorem을 사용하면 이분 그래프의 최대 매칭을 통해서 정점 덮개 (Vertex cover)를 찾을 수 있다. Dilworth's theorem을 사용하면 최소 Path cover를 이분 그래프의 최대 매칭으로 구할 수 있다. 실질적으로 문..

Petrozavodsk Winter 2020 Day9D. Data Structure Quiz $O((n + q_1 + q_2) \log^2 n)$ 풀이도 있고, $O(n^{5/3} + (q_1 + q_2) n^{1/3} \log n)$ 풀이도 있습니다. 두 번째는 통과를 하고, 첫 번째는 구현은 안 해 봤지만 아마 통과를 못 할 것 같습니다 :) 여기서는 $O((n + q_1 + q_2) \log^2 n)$ 풀이를 소개한 후 $O((n + q_1) \log^2 n + q_2 \log n)$ 풀이를 소개합니다. $x, y$ 축에 대한 2차원 세그먼트 트리 같은 것을 사용할 수 없으니, $x$ 축은 분할 정복, $y$ 축은 1차원 세그먼트 트리를 사용해서 관리하는 식의 접근을 사용합니다. 전반적인 철학은 O..