뉴비의 PS 낙서장

https://www.acmicpc.net/problem/1616 1616번: 드럼통 메시지 첫째 줄에 자연수 K, M이 주어진다. K는 2이상, M은 1이상인 자연수이다. 항상 KM ≤ 10,000,000을 만족한다. www.acmicpc.net 일단 길이가 \(M-1\) 개로 이루어진 모든 메시지에 대해 다음 메시지로 나올 수 있는 메시지들에 대해 간선을 이어준다. 이때, 간선의 가중치에는 추가되는 수가 부여된다. 아래의 경우는 \(K = 2\), \(M = 3\) 인 경우다. 여기서 오일러 경로를 사용해 지나쳐온 모든 간선들의 가중치를 저장해둔다. 저장된 값은 \(11101000\)이고, 놀랍게도, 저장된 메시지는 우리가 찾고자 하는 답이 된다. 시간 복잡도는 \(O(K^{M-1}*K)\) = \(..

www.acmicpc.net/problem/10169 10169번: 안전한 비상연락망 입력의 첫 줄에는 마을의 수 N (2 ≤ N ≤ 100,000)과 도로의 수 M (2 ≤ M ≤ 300,000)이 자연수로 주어진다. 각 마을은 1번부터 번호가 붙은 것으로 생각한다. 이후 M 개의 줄에는 각각 3개의 자연수가 주 www.acmicpc.net 도로 하나가 없어졌을때마다 mst를 구하는 문제다. 일단 두가지 경우로 나눌 수 있는데, i) 기본 mst에 포함되지 않는 도로인 경우 ii) 기본 mst에 포함된 도로인 경우 i)에 대해서는 답이 변하지 않는다는 것을 알 수 있다. 이제 ii)에 대한 처리가 문제인데, 일단 mst로 만들어진 도로로 트리를 만든다. 검은색 : mst에 포함된 도로, 빨간색 : 포함..

www.acmicpc.net/problem/18913 18913번: Graph Coloring You are given a tournament, represented as a complete directed graph (for all pairs $i,j$ of two different vertices, there is exactly one edge among $i \to j$ and $j \to i$), with $n \leq 3000$ vertices. You need to color its edges into $14$ colors. There www.acmicpc.net 내가 푼 문제중에 재밌던 문제의 풀이를 블로그에 올린다. 그래프의 간선들에 \(a\)~\(n\)의 색을 매길건데, 어떤 경로 \(x..