구사과

IOI 2020 Day 1 대회가 종료되었다. 올해 대회의 개최지는 싱가포르지만, COVID-19로 인하여 현장 대회는 취소되었다. 대회는 모두 온라인으로 진행되며, 한국 학생들은 서울에서 모여서 감독 하에 대회를 진행하고 있다. 한국 학생들의 성적은 다음과 같다. Day 1 기준이고, Day 2 점수를 감안하지 않았음을 유념하라. 최은수, 100 / 100 / 100, 300점, 1등 - 7등 송준혁, 75 / 100 / 100, 275점, 8등 - 13등 반딧불, 32 / 100 / 53, 185점, 61등 - 63등 임성재, 44 / 100 / 41, 185점, 61등 - 63등 특기할 점은 한국 학생들의 성적이 상당히 우수하다는 것이다. 최은수 학생은 300점 만점이라는 아주 훌륭한 성적으로 대회..

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를 이분 그래프의 최대 매칭으로 구할 수 있다. 실질적으로 문..