구사과

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

작년 가을에 버추얼 후기 느낌으로 적어놓고, 올리려고 하다가 여러 이유로 포스팅하지 않았던 글. 거의 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$에 대해 자연수 색상 을 배정하여 간선으로 직접 연결된 정점 쌍마다 다른 색상을 배정해야 한다. 이 때, 배정..

9. Dynamic Tree DP Dynamic Tree DP는 특수한 형태의 Tree DP를 최적화할 수 있는 방법으로, 일반적인 직선에서 행렬과 같은 구조를 사용하여 DP를 최적화하는 것과 비슷한 방식이다. 사실 Tree DP가 아니라 일직선에서 하는 DP 문제라 하더라도 최적화 방법이 자명하지 않기 때문에, 이 글에서는 먼저 일직선에서의 DP 최적화를 먼저 설명한다. (일직선에서의 이러한 DP 최적화를 부르는 말은 잘 모른다.) In Line 다음과 같은 문제를 생각해 보자. Problem. 길이 $N$ 의 배열이 있을 때, 다음 두 연산을 쿼리당 $O(\log N)$에 계산하여라. 원소 갱신: $A[x] := v$ 최대 부분합 쿼리: 부분배열을 골라, 그 안의 원소 합을 최대화하여라. 즉, $Ma..

Grand Prix of Gomel Ptz Winter 2020 Gennady Korotkevich Contest 5이다. kdh랑 같이 했다. 문제들이 너무 수학적 성향이 강해 내 취향은 아니었다. B: online FFT 테크닉으로 된다는데, 그 online FFT가 그냥 분할 정복 같아서 차라리 G 말고 이걸 할까 하는 후회가 있었다. 뭐 분할 정복을 시도 안 해 본 건 아니지만.. 300iq가 웃긴 풀이를 알려줬는데, $n + k$ 개의 결과를 $2n+k$ 개의 결과로 확장하는 방법이 있다. $2n+k$ 각각의 계수는 (self-convolution) + ($[x/2, x/2+k]$ 근처에서 튀어나온 계수 몇개 제거) 정도로 구할 수 있다. 우항은 $n+k$ 개의 결과가 있으면 $O(nk)$ 에 ..

8. Circular LCS 두 문자열 $S, T$ 가 주어질 때 둘의 LCS를 구하는 문제는 잘 알려져 있고, $n = |S|, m = |T|$ 일 때 $O(nm)$ 보다 빨리 하기 힘든 것으로도 유명하다. Circular LCS 문제는 $S$ 를 Cyclic shift 할 수 있을 때, 각 cyclic shift에 대해서 LCS를 계산하는 문제이다. 기호로 표현하면, 모든 $0 \le i \le |S| - 1$ 에 대해, $LCS(S[i:] + S[:i], T)$ 의 값을 계산하는 문제가 된다. 이 문제는 일반적인 LCS 계산법을 사용하면 쉽게 $O(n^2m)$ 에 해결할 수 있으니, 이 글에서는 더 빠른 풀이를 논의한다. Circular LCS라는 문제는 경시대회에 간혹 등장하긴 하나, 이 문제 자..

GCJ 2008 World Finals A. Juice 사과와 바나나 주스의 비율로 가능한 후보는 $N^2$ 개입니다. 단순히 생각하면 $10000^2$개이지만, 사과의 비율을 $i$번째 사람을 만족시키는 최소 비율로 하고, 바나나 주스의 비율을 $j$번째 사람을 만족시키는 최소 비율로 하여도 문제가 없기 때문입니다. 사과, 바나나 주스의 비율을 고정하면 당근 주스의 비율이 $10000-A-B$와 같이 자동적으로 정해집니다. 사용할 사과 주스의 비율 $A$를 고정시킵시다. 이제 각각의 사람을 순서대로 고려합니다. 만약에 어떤 사람이 원하는 사과 주스의 비율이 $A$를 초과하면 무시해 줍니다. 그렇지 않은 경우, 이 사람이 원하는 바나나/당근 주스의 비율이 $B, C$ 라고 하면 $B_i \le B, C_..

4. Knuth's Optimization Recurrence: $DP[i][j] = Min_{i \le k < j}(DP[i][k] + DP[k + 1][j] + C[i][j])$ Condition: $C[i][j]$ is a Monge array, and satisfies $C[a][d] \ge C[b][c]$ for $a \le b \le c \le d$. Naive Complexity: $O(n^3)$ Optimized Complexity: $O(n^2)$ Knuth Optimization은 어떠한 구간을 쪼개는 형태의 동적 계획법을 최적화한다. Optimal Binary Search Tree 라고 알려진 문제를 Knuth가 $O(n^2)$ 동적 계획법으로 해결할 때 사용되었기 때문에 Knuth의..