구사과

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

(Lecture note is essentially an English version of this post. Slides are used for presentation.) 원 논문 (arxiv) 그래프의 최소 컷 (Minimum cut) 은 그래프를 연결되지 않게 하기 위해서 지워야 하는 간선 가중치의 최소 합이다. 가중치가 없는 경우에, 최소 컷은 그래프의 connectivity 를 정의하는 수량이 된다. 고로 최소 컷은 그래프가 주어졌을 때 계산하고 싶은 가장 기초적인 수량에 해당되며, 응용 예시 또한 무수히 많다. 그래프의 최소 컷을 계산하는 방법은 크게 3가지가 있다. 아래에 해당 방법의 발견 시간 순으로 나열한다. (아래 요약은 이 논문에서 따왔다.) Min-cut Max-flow 접근. Gl..

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

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

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

이 글은 https://codeforces.com/blog/entry/75431 의 한글 번역본입니다. 가능하면 원문을 보는 것을 추천합니다 ;) 그래프 $G$가 주어질 때, 각 정점 $v$에 대해 자연수 색상 을 배정하여 간선으로 직접 연결된 정점 쌍마다 다른 색상을 배정해야 한다. 이 때, 배정된 최대 색상을 최소화해보자. 즉, 서로 다른 색의 수를 최소화해야 한다. 이 문제는 그래프의 정점 색칠 (Graph Coloring, Vertex Coloring) 문제로, NP-complete임이 잘 알려져 있다. 너무 어려우니까 다른 문제를 생각해 보자. 그래프 $G$가 주어질 때, 각 간선 $v$에 대해 자연수 색상 을 배정하여 간선으로 직접 연결된 정점 쌍마다 다른 색상을 배정해야 한다. 이 때, 배정..

조만간 2020.05.11(?) problem solving이 올라옵니다. 그 글의 일부였는데, 좀 길어서 분리했습니다. https://www.acmicpc.net/problem/17405 Step 1 $gcd(F_i, F_j)$ 자체가 너무 커서 주어진 식 그대로는 다항 시간에도 계산을 할 수 없습니다. 하지만, $gcd(F_i, F_j) = F_{gcd(i, j)}$ 임이 잘 알려져 있기 때문에, 이 식을 쓰면 문제는 $\sum_{i = 1}^{n} \sum_{j=1}^{n} gcd(i, j)^k F_{gcd(i, j)}$ 가 됩니다. 항의 계산 결과가 gcd에만 의존함에 주목하십시오. $f(k) = 1 \le i, j \le N, gcd(i, j) = k$ 인 $i, j$ 의 수라고 하면, 위 식은..