주간 PS 리뷰
이번 한 주는 IOI 2008 문제 + 몇 개 풀면서 나름 알차게 푼 거 같다. 요즘 내신 수학과 PS를 격일로 하고 있는 이 정도 풀었으면 나쁘지 않다. 개인적으로 뿌듯하기도 하다. 다만 반성할 점은 블로그 글을 안 쓰고 넘어갈 뻔했다는 정도인 것 같다. 다음주는 oj.uz에 막 올라온 따끈따끈한 JOISC 2020을 풀어보려고 한다.
IOI 2008
https://www.acmicpc.net/category/detail/527
IOI 2008을 아직 풀지 않은 pyramid base 빼고 묶어서 리뷰해보려고 한다.
Type printer
주어진 단어들을 트라이로 만들고 한 번 순회하면 답이다. 그런데 마지막 리프에 도달한 후에는 다시 올라올 필요가 없으므로 총 연산 수는 마지막 단어의 길이에만 좌우된다. 따라서 순회를 가장 깊은 노드를 마지막에 들어가도록 잘 하면 된다. 하지만 트라이를 직접 만드는 일은 번거로우므로 그냥 단어들을 정렬해서 안 맞는 활자만 바꾸는 방식으로 했다. 이게 더 문제에서 주어진 설명에 가깝지만 트라이랑 원리는 똑같다. 가장 깊은 단어를 마지막에 찍는 건 정렬기준에서 단어의 위치별로 가장 긴 단어에 들어간 글자를 Z보다 큰 문자로 놓고 나중에 다시 잘 바꾸면 된다. 구현이 매우 짧고 쉽다.
Island
우선 페리? 의 존재 때문에 컴포넌트 별로 단순히 최장 경로를 구해서 합치면 된다. 따라서 하나의 컴포넌트에서 최장 경로를 찾는 방법만 알아내면 된다. 일반적인 그래프의 최장 경로라면 문제가 어렵겠지만 문제의 그래프는 Functional Graph이다. (말 그대로 함수를 그래프로 표시한 것. 각 정점마다 out degree가 1) 따라서 그래프에는 단 하나의 사이클이 있고, 사이클 위의 정점들을 루트로 하는 트리들이 사이클에 꿰여있는 형태이다. 이 그래프에서 최장경로는 아래의 두 가지 케이스 중 하나이다.
i) 사이클의 간선을 포함하지 않는다.
사이클을 지나지 않는다는 말은 분리한 트리들 중 하나에서만 경로를 이룬다는 말과 같다. 따라서 트리에서의 최장경로이니 그냥 트리의 지름을 O(N)에 찾아주면 된다.
ii) 사이클의 간선을 포함한다.
이 경우 사이클에서 경로에 포함된 간선은 자명히 구간을 이룬다. 또 단순경로라는 조건에 의해 한 번 트리의 안쪽으로 내려가면 돌아올 수 없으므로 트리의 간선을 사용하는 것은 양 끝 루트에서밖에 불가능하다. 따라서 경로의 길이는 (사이클 위 구간의 길이)+(양 끝 트리의 최대깊이 합)이 된다. 최대 깊이는 O(N)에 잘 순회해서 구하면 된다. 이제 여기서 위 식을 최대화하는 것은 그냥 쭉 사이클 위를 돌면서 최댓값을 관리하면 된다. 좀 더 구체적으로 설명하자면, 우선 임의로 사이클을 잘라서 편다. 사이클의 총 길이를 L이라고 하고 1번에서 i번까지의 거리를 Si, i번 루트의 최대 깊이를 Ai라고 하자. 이들은 모두 선형에 전처리 할 수 있다. 양 끝점을 u, v (u<v)라고 하면 나올 수 있는 총 거리는 (Au+Av)+(Sv-Su) 또는 (Au+Av)+(L-Sv+Su)이다. u항과 v항이 독립적이므로 v를 1부터 증가시키면서 Au+Su와 Au-Su의 최대를 각각 관리하면 선형에 답을 구할 수 있다.
따라서 이대로 잘 구현하면 된다. 하지만 N=10^6의 영향인지 메모리 초과가 매우 쉽게 일어난다. (재귀 스택이 원인으로 추정?) 나는 ojuz에서 재귀에 inline을 붙이고 맞은 뒤 백준에서 AC받는것은 정신건강을 위해 포기했다. 재귀 없이 BFS등으로 잘 짜면 될 거 같다.
Fish
관찰을 많이, 열심히 하면 된다. 핵심은 경우의 수 문제 답게 중복을 없애는 것인데, 이를 잘 설계하면 된다. 제일 먼저 생각할 수 있는 사실은 우리가 배를 가를 생선은 결국 하나이고, A가 B를, B가 C를 먹을 수 있다면 A가 C를 먹을 수 있다는 사실이다. 위의 두 가지 관찰에서, 연쇄적으로 잡아 먹을 필요없이 물고기 하나가 아무것도 먹지 않은 물고기들을 먹는 경우만 봐도 모든 경우를 고려할 수 있다는 사실을 알 수 있다. 따라서 모든 보석 조합을 '최종적으로 누구의 배에 들어있을 것인가?' 를 기준으로 대응시키고 각 물고기 별로 대응된 조합의 수를 세어주면 답이 됨을 알 수 있다.
이것으로는 관찰이 많이 부족하니 일단 크기 순으로 정렬을 해보자. 이때 크기가 작은 물고기가 먹을 수 있는 조합은 큰 물고기가 먹을 수 있는 조합의 부분 집합이다. 중요한 점은 본인이 원래 가진 보석을 고려하지 않고, 먹는 조합으로만 보았을 때 성립한다는 점이다. 단, 확실한 점은 같은 보석을 가지고 있는 두 물고기는 길이가 긴쪽이 조합을 완전히 포함하므로 가장 큰 물고기에서 모든 경우를 세줘도 된다는 점이다.
두 물고기의 보석이 다른 경우는 어떻게 될까? 작은 물고기에만 포함되고 큰 물고기에는 포함되지 않는 경우를 생각해볼 수 있는데, 이때는 단 두가지의 케이스 밖에 없다. 큰 물고기의 보석을 A, 작은 물고기의 보석을 B라고 하면 큰 물고기는 자신의 보석을 뱉을 수는 없으므로 A가 1개 이상 무조건 포함된다. 따라서 작은 물고기가 A를 단 하나도 먹지 않는 조합은 작은 물고기에만 해당되는 경우이다. 다른 하나는, 둘이 먹을 수 있는 최대 B의 양이 같을 때 원래 뱃속에 있던 B 때문에 큰 물고기가 먹을 수 있는 보석보다 하나 더 많이 먹을 수 있는 경우이다. 이 외 종류의 보석은 큰 물고기에게 먹히는게 무조건 더 많으므로 차집합이 생길리가 없다.
위의 정리된 사실들을 이용하여, 곱을 관리하는 세그먼트 트리를 만들면 쉽게 각 물고기의 경우의 수를 세줄 수 있다. 여기서의 방법은 각 보석 별로 가장 긴 물고기의 위치를 기준으로 보석 번호를 다시 지정하면 구간 쿼리를 이용해 계산할 수 있다. 사실 구현이 그렇게 간단하지는 않고 이후에도 성가신 중복 문제들을 고려해야 한다. 하지만 위의 관찰들로 인해 대부분 해결된다. 마지막으로 경우의 수 모듈라 문제에서는 항상 오버플로우와 음수모듈라를 조심하도록 하자.
Linear Garden
그다지 어렵지 않은 DP 문제이다. 시작점을 '어떤 구간을 잡아도 개수 차이가 2이하' 라는 조건은 누적합으로 L=1, P=-1로 생각하면 전체에서 최소값과 최댓값 차이가 2이하임을 의미한다. 이를 이용해 경우의 수를 잘 계산해 주고 사전순 구하기는 그냥 P가 나올때마다 해당 자리를 L로 바꿨을때 뒤로 가능한 경우의 수를 세서 더하는방식으로 간단히 해결할 수 있다.
Telepoters
각 텔레포터 위치에 정점을 두 개씩 만든다고 생각하자. 하나는 텔레포트로 이동하는 나가는 간선이 연결되고, 하나는 들어오는 간선이 연결된다. 그리고 나가는 간선은 이전 위치에서 걸어오는 간선, 들어오는 간선은 다음으로 걸어나가는 간선이 연결된다. 이렇게 만들면 그래프는 몇 개의 컴포넌트로 나누어지는데, 처음과 끝이 포함된 체인 한 개와 단순 사이클들이 만들어진다. 한 컴포넌트를 지나가면 그 중 텔레포트의 횟수는 정점 수의 절반이다. 여기에 텔레포터들을 추가하면 사이클을 체인에 한 개씩 이을 수 있다. 따라서 답은 사이클을 크기순으로 정렬하고 앞에서 K개를 뽑아 답에 더한 뒤, 체인의 텔레포트와 2*K (추가한 텔레포터의 텔레포트)를 더한 값이다. 주의할 점은 K가 사이클 수보다 클 때는 사용되고 남은 텔레포트에 2를 곱하는것이 아니라 홀수일 경우 1을 빼주어야 한다는 것이다. 텔레포터 두 개를 교차시켜 놓으면 4번을 다 지나는데 세 개로는 만들 수가 없다. 따라서 두 개씩 짝 짓고 하나를 따로 놓아서 1개를 빼주어야 한다. 컴포넌트의 관리는 유니온 파인드로 했다.