구사과

(2020.11.24 01:27 - 모든 문제를 구현해서 풀이를 검증했으며, 일부 풀이를 고쳐 적었다.) (2020.11.23 01:32 - 모든 문제에 대한 풀이를 올렸다.) Result Analysis 이번 서울 리저널에서의 각 대학 별 상위 팀은 다음과 같다. 서울대학교: Let Us Win ICPC WF (World Finals 진출 확정) KAIST: Everybody (World Finals 진출 매우 유력) 고려대학교: 1_Hoeaeng_2_Hawawang (World Finals 진출 예상) 숭실대학교: 181920 (World Finals 진출 가능성 있음) 성균관대학교: we need sleep 올해 서울 리저널은 관전자 입장에서 재밌게 볼 만한 요소가 아주 많은 대회였다. 그래서 관전..

원래는 블로그 글을 좀 자세하고 정확하게 쓰려고 노력하는 편이나, 인터넷 예선은 채점해 보기도 까다롭고 하니 그냥 대충 정리해서 올리려고 한다. 완전 입풀이고, 코드를 한 줄도 안 짜보고 올리는 글이라서, 내용이 부정확할 수도 있다. (10/20 추가: 현재 C H 빼고 모두 채점이 된다. 해당 문제들에 대해 블로그에 나온 방식으로 구현해서 전부 정답을 받았다.) A 최종 정렬된 배열을 생각해 보자. 이 배열의 부분배열(연속) 중 원래 입력으로 주어진 배열의 subsequence를 만족하는 최대 길이의 부분배열을 찾으면 된다. 중복이 없으면 그냥 원래 배열에서의 index가 증가하는 최대 길이 부분배열을 찾으면 된다. 아닌게 귀찮은데.. substring 상 서로 다른 원소가 1개, 2개, 3개 이상인 ..

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

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..

POI 1996. Canoes 먼저 각각의 사람을 몸무게 순으로 정렬해 놓읍시다. 가장 가벼운 사람은 다른 사람과 보트를 태워 보내는 것이 합리적으로 보이니, 가장 가벼운 사람을 보낼 때는, 다른 사람 한 명을 잡아서 같이 보트를 태워 보냅니다. 같이 탈 수 있는 사람이 여럿이면 물론 몸무게가 무거운 사람을 보내는 것이 현명합니다. 두 번째, 세 번째로 가벼운 사람들에게 이를 반복하고, 같이 태워 보낼 수 있는 사람이 없을 때까지 이를 반복합니다. 이 알고리즘의 구현은, 정렬된 배열에서 현재 보낼 무거운 사람의 “포인터” 를 가지고 있으면 간편합니다. 가벼운 사람이 있을 때, 이 사람의 몸무게를 맞출 수 있을 때까지 포인터를 앞으로 (몸무게가 감소되는 쪽으로) 내려주고, 그 사람과 매칭시킨 후, 포인터를..

작년 가을에 버추얼 후기 느낌으로 적어놓고, 올리려고 하다가 여러 이유로 포스팅하지 않았던 글. 거의 1년동안 하드에서 잠자고 있던 텍스트다! 포스팅을 미룬 이유는 여러가지가 있다. 당연히 제일 큰 이유는 귀찮고 관심 없었기 때문이지만, 나름대로 통신교육 자료로 사용하려는 목적도 있었고, 업솔빙을 적당히 하고 보완해서 올리려는 목적도 있었다. 통신교육에는 이미 충분히 우려먹은 것 같아 별 상관이 없어 보이고, 업솔빙은 끝이 없을 것 같아서 그냥 올린다. 여담으로 여기 언급된 문제중 2019 가을 통신교육에 총 9문제가 사용되었다. 알아서 잘 찾아보자. Day 5/6/8에 대해서는 Part 2에 적을 예정이다 (이건 적어 놓은 게 없다. 아주 먼 미래에 올라올 듯 :p) Day 3/4/7에 대해서는 딱히 ..

Matroid Intersection 관련 발표를 할 일이 생겨서, 발표 자료와 과제를 공개합니다.

옛날에 어디 적어두었던 내용들을 공개합니다. 적어둔 시점이 달라서 문체 역시 문제마다 다를 수 있습니다. 유의해주세요. (사실 문체는 적어둔 시점이 같아도 달라지는 경우가 많긴 합니다...) Codeforces #620 Div2B. Longest Palindrome 문자열의 길이가 같으니까 많은 문자열을 모아두면 됩니다. 모은 문자열의 개수가 짝수라고 가정하면, 해당 문자열, 그리고 그것을 뒤집은 문자열로 매칭되는 쌍을 최대한 많이 모아주면 됩니다. 모든 문자열이 다 다르고, 제한이 작기 때문에, 그리디하게 매칭해 주면 됩니다. 홀수라고 가정하면, 중간에 팰린드롬이 하나 와야 합니다. 모든 문자열이 다르니까 팰린드롬은 매칭에 들어가지 않습니다. 고로 매칭되지 않은 팰린드롬이 있었다면 중간에 끼워넣으면 됩..