etyu

JOI 2021. Robot 로봇이 이동할 경로를 미리 정한 뒤 최소 비용을 계산한다고 생각하자. 정점 \(u\)에서 정점 \(v\)로 이동할 때 색깔을 바꾸는 방법은 다음 2가지이다. \((u, v)\)의 색깔을 바꾼다. \(u\)에 인접한 간선 중 \((u, v)\)와 색깔이 같으면서 \((u, v)\)가 아닌 간선들의 색깔을 모두 바꾼다. 그러므로 각 간선에 대해 방향성을 부여하고, 두 방법의 비용 중 더 적은 것을 간선의 가중치로 설정하여 1번 정점에서부터 \(N\)번 정점까지의 최단 경로를 구하는 방법을 생각할 수 있다. 하지만 1번 방법을 사용한 직후에 2번 방법을 사용하면 간선의 비용이 중복되서 계산될 수 있다는 문제가 있다. 현재 1번 방법으로 원래 색깔이 \(c\)인 간선 \((u, v)..

(이 글은 독자가 Splay tree, link/cut tree를 이해하고 있다고 가정하고 설명한다.) Top tree는 동적 트리 (간선의 추가, 제거가 일어나는 트리)를 관리하는 자료구조이다. Top tree는 path 쿼리와 subtree 쿼리를 모두 지원하며, 트리의 diameter, center, median과 같은 일반적인 자료구조에서 관리하기 힘든 값들을 관리할 수 있다. 이 글은 Self-Adjusting Top Tree 논문에 기반하여 Top Tree의 구현에 대해 설명한다. (이 논문에 대해서 구사과님이 쓰신 글도 있다.) Top tree 직선형 구조를 관리하는 자료구조인 세그먼트 트리는 전체 배열을 여러 구간으로 분리하고, 이 구간들을 합치는 과정을 트리로 관리한다. Top tree는..

JAG Practice Contest 2020 D. Surround the Castle 성을 둘러싸는 것은 격자에서 상하좌우로 이동하며 사이클을 만드는 것으로 볼 수 있으므로, 성을 둘러싸는 최단 경로를 찾는 방식으로 접근합니다. 성을 둘러싸는 경로만을 생각해야 하는데, 이는 성에서 반직선을 하나 그어 그 선을 홀수 번 지나는 경로만을 생각하면 됩니다. (반직선을 그어 다각형 내부에 있는지 판별하는 것과 비슷한 방식) 그러므로 반직선을 홀수 번 지난 상태와 짝수 번 지난 상태를 구별하여 다익스트라를 돌리면 문제를 해결할 수 있습니다. 다익스트라의 시작점을 잡아야 하는데, \(R\)의 범위가 작으므로 성의 위쪽이나 아래쪽을 전부 해보면 됩니다. BOI 2021 A. A Difficult(y) Choice ..

Innopolis Open, Second elimination round, 2018-2019 D. Game of Wizards 일단 마지막에 남은 포션의 개수는 생각하지 않고 누가 이기는지만 구해봅시다. 상대의 포션을 없앨 때, 상대의 포션 중 가장 왼쪽에 있지 않은 포션을 없애는 것은 다음 상대의 턴에 영향을 주지 않으므로 나중에 없애도 됩니다. 그러므로 가장 왼쪽부터 몇 개의 포션을 없애는지만 생각합니다. 다음과 같은 DP 식을 정의합니다: (플레이어는 편의상 선공을 \(0\), 후공을 \(1\)이라 하겠습니다.) \(D[p][q][x][y][t]\) = 선공이 남은 포션의 개수가 \(p\), 후공이 남은 포션의 개수가 \(q\), 선공이 남은 마나가 \(x\), 후공이 남은 마나가 \(y\), 현재..

Dynamic Connectivity Problem(동적 연결성 문제)란, 다음과 같은 쿼리를 처리하는 문제를 말합니다. 임의의 간선 추가 임의의 간선 삭제 어떤 두 정점 사이에 경로가 존재하는지 판별 이 문제는 분할 정복을 통해 오프라인으로 풀 수 있지만, 이 글에서는 온라인 풀이를 설명합니다. 그래프가 포레스트일 때 포레스트에서는 Link-Cut Tree나 Euler Tour Tree를 사용하여 풀 수 있습니다. 이번에는 Euler Tour Tree를 사용합니다. 어떤 트리를 Euler Tour로 나타낸 수열에서 그 트리를 복원할 수 있기 때문에 각 트리를 트리 자체가 아닌 Euler Tour로 관리합니다. 이렇게 관리하면 간선의 추가, 삭제는 이 수열을 끊고 연결하는 연산들로 대체할 수 있습니다. ..

이 글은 다음 논문(EERTREE: An Efficient Data Structure for Processing Palindromes in Strings)을 바탕으로 작성된 글입니다. 이 글의 그림은 이 논문에서 가져왔습니다. 개요 Eertree는 문자열의 회문을 관리하는 자료구조입니다. Eertree를 설명하기에 앞서, 몇가지 정의를 내리고 시작하겠습니다. 문자열은 \(w = w[1..n]\)과 같이 표현하고, 문자열의 i번째 문자는 S[i]와 같이 표현합니다. 문자의 종류의 수를 \(\sigma\)로 표현합니다. 어떤 \(i, j\)에 대해 \(u = w[i..j]\)라면 \(u\)는 \(w\)의 부분 문자열(substring)입니다. 어떤 \(i\)에 대해 \(u = w[1..i]\)라면 \(u\)..

홀의 결혼 정리(Hall's marriage theorem)는 여러 개의 집합이 주어졌을 때, 각 집합에서 서로 다른 수를 고를 수 있는 필요충분조건에 대한 정리입니다. 홀의 결혼 정리에 의하면, 집합들의 집합 \(S = \{A_1, A_2, \dots, A_k\}\)가 주어졌을 때 각 집합에서 서로 다른 수를 고를 수 있다는 것은 어떤 \(S\)의 부분집합 \(W\)을 선택하더라도 \(W\)의 원소들의 합집합의 크기가 \(|W|\) 이상이라는 것과 동일합니다. CERC 2016. Bipartite Blanket 더보기 먼저 이분 그래프의 두 정점 집합에서 매칭이 존재하는 정점 부분집합을 따로 구해봅시다. 전부 \(O(2^n + 2^m)\)개의 경우가 있으므로 각각 홀의 결혼 정리를 만족하는지 검사한 뒤..

처음으로 블로그를 만들어 봤다. 무엇을 적어야할지 잘 모르겠어서 일단 재밌었던 문제의 풀이를 몇 개 적어봤다. PPC 2018 F. Edge Coloring 그래프가 트리일 경우를 생각해 봅시다. 트리의 리프에서부터 루트 아래까지 올라가며 부모 정점으로 가는 간선을 색칠할 때 리프일 경우, 무조건 색칠 리프도 루트도 아닐 경우, 자식으로 가는 간선 중 색칠된 간선이 짝수일 경우 색칠 이러한 방식으로 각 간선의 색칠 여부를 유일하게 결정할 수 있습니다. 색칠 후에 루트 정점의 차수는 짝수일 수도 홀수일 수도 있는데, 모든 정점의 차수 합은 항상 짝수이므로 \(n\)이 짝수일 때 루트 정점의 차수는 홀수가 됩니다. 그러므로 그래프가 트리일 때는 \(n\)이 짝수면 \(1\), 홀수면 \(0\)이 답이 됩니다..