티스토리 뷰

온라인 아카이브 링크


A. The Mountain of Gold?


0번 도시에서 시작하고 시공간을 이동할 수 있는 수단들이 주어졌을 때, 0번 도시의 과거로 돌아올 수 있는지 판별하는 문제다.

일반적으로 $O(NM)$ 시간복잡도의 Bellman-ford 알고리즘은 전체 그래프에서 음수 싸이클이 있는지 판별할 때 쓰인다. 이 문제에서는 0번 도시와 강하게 연결된 연결 요소(0번 도시에서 $x$로 갈 수 있고, $x$에서 0번 도시로 올 수도 있는 $x$들의 집합)에서 음수 싸이클이 있는지 Bellman-ford로 $O(NM)$만에 확인해주면 된다.


코드 보기


B. Sequence


이진수열이 주어지고 하나의 비트를 뒤집을 수 있는 연산을 $K$번 할 수 있을 때, 모두 0으로 만드는 경우의 수를 구하는 문제다.

Dynamic Programming으로 해결할 수 있다.

아래와 같이 다이나믹 배열을 정의하자.

D[i][j] = i번의 연산이 남았고 1의 개수가 j개 일 때, 모두 0으로 만드는 경우의 수

점화식은 아래와 같다.

D[i][j] = j * D[i-1][j-1] + (N-j) * D[i-1][j+1]

시간복잡도는 $O(NK)$ 다.


코드 보기


C. Turtle Graphics


거북이의 시작 위치와 이동 명령이 주어졌을 때, 거북이의 최종 좌표와 두 번 이상 방문한 점의 개수를 세는 문제다.

문제에서 하라는대로 하면 된다.


코드 보기


D. Circle and Marble


트리가 주어지고, 각 노드마다 구슬이 여러 개 있을 수 있다. 두 명이서 게임을 하는데, 각 차례마다 구슬 하나를 선택해 구슬이 있는 노드의 자식 노드로 움직일 수 있다. 만약 자기 차례에 더 이상 움직일 수 있는 구슬이 하나도 없는 경우 진다. 두 명 모두 최적의 전략으로 게임에 임할 때, 누가 이기는지 구하는 문제다.

주어진 트리에서 노드 별로 Grundy Number를 구한다. 각 구슬마다 자신이 있는 노드의 Grundy Number를 XOR 했을 때 결과가 0이면 처음 시작하는 사람이 지고, 0이 아니면 처음 시작하는 사람이 이긴다. 각 노드에 있는 구슬의 개수가 많지만, 구슬 개수의 홀짝성을 이용하면 쉬워진다.

문제에서 가능한 Grundy Number는 최대 14다. 트리 구성에서 노드의 Grundy Number가 $g$이기 위해서 그 노드의 서브 트리에 있는 노드 개수가 최소 $2^g$개 필요하기 때문이다.


코드 보기


E. Group of Strangers


정점이 $N$개고 간선이 $M$개인 무방향성 그래프가 주어진다. 이 그래프에서 정점 3개를 선택하는데 선택 된 저점들이 서로 연결이 되어 있지 않은 것의 개수를 세는 문제다.

처음으로 $O(NM)$ 방법을 생각할 수 있다. 문제 데이터는 $O(NM)$ 방법보다 빠른 방법을 요구한다. 우선, 문제를 역으로 생각해서 간선이 적어도 하나라도 연결되어 있는 세 정점을 찾는 것으로 바꾼다. 그리고 차례대로 3개의 간선으로 연결되어 있는 세 정점 개수, 간선 2개로 연결되어 있는 세 정점 개수, 간선 1개로 연결되어 있는 세 정점 개수를 센다.

간선 3개로 연결되어 있는 세 정점의 개수는 그래프에서 그려지는 삼각형의 개수와 같다. 이 개수를 $O(M^{1.5})$으로 구할 수 있다.

우선 $N \leq 5000$이므로 임의의 두 점 사이에 간선이 연결되어 있는지 배열을 이용하여 $O(1)$만에 구할 수 있다. 차수가 $\sqrt{M}$ 이상인 정점들을 무거운 정점이라 하자. 무거운 정점의 개수는 $\sqrt{M}$ 이하다. 무거운 정점 3개로 이루어진 삼각형은 $(\sqrt{M})^3 = O(M^{1.5})$으로 해결 가능하다. 마찬가지로 무거운 간선을 정의할 수 있는데, 무거운 정점 두 개를 연결하는 간선을 무거운 간선이라 부르자.

무거운 간선이 아닌 간선이 연결하는 두 정점 $a$, $b$ 중 차수가 작은 정점을 $a$라 하자. 정의에 따라 $a$는 무거운 정점이 아니다. 때문에 $a$의 차수는 $\sqrt{M}$ 이하다. 이제 이 간선과 $a$에 연결된 다른 간선들을 모두 묶어보고 삼각형이 되는지 확인하면 된다. 이 시간복잡도도 $M \times \sqrt{M} = O(M^{1.5})$가 된다.

이제 간선 2개로 연결되어 있는 세 정점의 개수는 $O(N)$ 만에 구할 수 있다. 차수가 $d$인 정점 $i$를 포함한 간선 2개로 이루어질 수 있는 세 점의 개수는 ${d}\choose{2}$가 된다. 이를 다 더한다. 이 중에 삼각형이 있을 수 있는데, 더한 값을 삼각형 개수에 비례하게 뺀다.

마찬가지로 간선 1개로 연결되어 있는 세 정점의 개수도 $O(N)$ 만에 구할 수 있다. 차수가 $d$인 정점 $i$를 포함한 간선 1개로 이루어질 수 있는 세점의 개수는 $d \times (N - d - 1)$이다. 이를 다 더한 뒤, 앞에서 구한 간선 2개로 이루어질 수 있는 세 점 개수에 비례하여 값을 빼주면 된다.

총 시간복잡도는 $O(M^{1.5} + N)$이 된다.


코드 보기


F. Pantun Grader


ICPC에 종종 등장하는 영어 문제다. 문제에서 하라는 대로 하면 된다. strtok 함수를 쓰면 쉽게 구현할 수 있다.


코드 보기


G. Hari Merdeka


$N$개의 알파벳이 주어지고, 각 알파벳을 쓰는데 비용이 주어진다. $M$개의 단어가 주어지고, 각 단어마다 문장에 등장 했을 때 얻는 점수가 주어진다. 쓰는데 비용 $B$를 넘지 않는 문장을 쓸 때, 단어 등장 점수의 합이 최대가 되는 문장의 점수를 구하는 문제다.

문제에서 주어지는 단어들을 가지고 Aho-Corasic Trie를 만들면 노드 개수가 최대 10,000개가 된다. Dynamic Programming으로 각 Aho-Corasic의 상태별로 돈을 $b$ 만큼 썼을 때 얻을 수 있는 최대 점수를 구한다. 총 시간복잡도는 $O(NM|W|B)$가 된다.


코드 보기


H. Túnel de Rata


$S$개의 정점과 $L$개의 간선으로 이루어진 무방향성 그래프가 주어진다. 각 간선에는 길이가 있다. 간선에 카메라를 설치할 때, 설치 비용은 간선 길이와 같다. 그래프에서 모든 싸이클에 대해 싸이클에 속한 간선 중 적어도 하나에는 카메라를 설치하고 싶다. 이 때 카메라를 설치하는 최소 비용을 구하는 문제다.

어떤 간선에 카메라를 설치하면 그 간선이 포함된 싸이클에 대해서는 문제의 조건을 만족시켜준다. 따라서 카메라를 설치한 간선들을 다 지웠을 때 그래프에 싸이클이 존재하지 않으면 된다. 이제 문제는 전체 그래프에서 Maximum Spanning Tree를 구하는 것과 같다.


코드 보기


I. Best Position


'G'(grain)와 'L'(livestock) 두 문자로 이루어진 $R \times C$ 크기의 직사각형이 있다. 마찬가지로 $H \times W$ 크기의 작은 직사각형이 주어진다. 작은 직사각형을 전체 직사각형에 뒤집지 않고 같은 문자의 개수가 최대화 되게 배치하는 문제다.

이 문제는 FFT(Fast Fuorier Transform, 고속 푸리에 변환)으로 해결할 수 있다. 큰 직사각형을 $RC$ 크기의 이진수열로 나타내는데, 위치에 있는 값이 'G'인 경우 1, 아닌 경우 0으로 나타낸다. 마찬가지의 규칙으로 작은 직사각형에 대해서는 $(H-1)C + W$ 크기의 이진수열로 나타낸다. 그런 뒤 FFT를 통해 convolution을 구하면 각 부분직사각형 위치마다 매치되는 'G'의 개수를 구할 수 있다. 마찬가지로 각 부분직사각형 위치마다 매치되는 'L'의 개수를 구할 수 있다. 시간복잡도는 테스트케이스별로 $O(RC \lg RC)$다.


코드 보기


J. Spokes Wheel


32비트 이진수 A, B가 16진수 형태로 주어진다. A를 최소 회수로 회전시켜서 B를 만들 수 있는 방법을 구하는 문제다.

문제에서 하라는 대로 하면 된다. 32비트 이진수를 unsigned int로 나타내고 비트 연산자를 이용해 쉽게 코딩할 수 있다.


코드 보기


K. Ball


'W' (White), 'R' (Red), 'G' (Green) 중 하나의 색으로 색칠되어있는 공 $L$개가 원형으로 배치되어 있다. 단위 시간이 지나면 특정 규칙에 따라 공의 색이 변한다. 단위 시간 $N$이 지났을 때, 각 색 별로 공이 몇 개 있는지 구하는 문제다.

'W'를 0, 'R'을 1, 'G'를 2로 나타내자. 그러면 단위 시간이 지났을 때 변하게 되는 공의 색은 (자기 색 + 오른쪽 공의 색)을 3으로 나눈 나머지가 된다. 현재 색을 $a_i (0 \leq i < L)$로 나타내자. 단위 시간이 한 번 지났을 때 공의 색을 $b_i$로 나타내면 $b_i = a_i + a_{i+1}$이 된다.

단위 시간이 세 번 지났을 때 공의 색을 $c_i$로 나타내면 $c_i = a_i + 3a_{i+1} + 3a_{i+2} + a_{i+3}$가 된다. 이를 3으로 나눈 나머지이므로 정리하면 $c_i = a_i + a_{i+3}$이 된다.

마찬가지로 단위 시간이 아홉 번 지났을 때 공의 색을 $d_i$로 나타내면 $d_i = a_i + a_{i+9}$가 된다. 그렇다는 것은 단위 시간이 $3^k$번 지난 이후 $i$번 공의 색은 $a_i + a_{i+3^k}$가 된다는 것이다. 이를 통해 단위 시간 $N$이 지났을 때 공의 색을 $O(L \log N)$ 만에 구할 수 있다.


코드 보기



댓글
댓글쓰기 폼