구사과

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

Matroid Intersection 관련 발표를 할 일이 생겨서, 발표 자료와 과제를 공개합니다. 과제 풀이는 6월 2일 오후 9시에 이 글에 추가하겠습니다.

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