IOI 2008 Day 1 Solutions

1. Type Printer

겨울학교에서 문자열 셋을 돌때 나왔던 문제. 간단히 주어진 문자들로 Trie를 구성한다음 트리 순회를 그리디하게 진행하면 된다. 각 노드별로 서브트리에 있는 노드중 가장 깊은 원소의 깊이(=서브트리의 높이)를 전처리한 뒤 그 값이 작은 자식노드쪽부터 재귀함수를 호출하면 된다. 시간복잡도는 Trie의 노드 개수로 O(NS)이다. (S는 각 문자열의 길이)

 

2. Fish

물고기의 뱃속에서 나올 수 있는 보석의 쌍의 개수를 구하는 문제이다. 이 문제에서 중요한 것은 중복되지 않게 이러한 쌍들을 잘 세주는 것인데, 그러기 위해 몇가지의 관찰을 하자.

 

(1) 각 보석 종류에 대해 가장 길이가 긴 물고기에 대해서만 쌍을 세줘도 된다.

pf) 조금만 생각해도 자명한 사실이다. 그보다 짧은 물고기가 먹을 수 있는 보석의 multiset은 가장 긴 물고기가 먹을 수 있는 보석의 multiset의 부분집합이기 때문.

 

각 보석별로 가장 긴 물고기의 길이에 대한 오름차순으로 번호를 다시 매겨주자.

 

일단, i번 보석을 가진 가장 긴 물고기에 대해 j<=i인 보석 j들의 집합만을 고려한 상태에서 그 물고기를 건졌을때 가능한 보석의 쌍의 개수를 구해주자. 투포인터를 이용해 이 물고기의 길이가 L일 때 L/2이하인 물고기들에 대한 보석의 개수 G[1], G[2], ..., G[k]를 유지해주었을 때 답은 (1+G[1])*(1+G[2])*...*(1+G[i])이다. 각각의 i에 대해 이를 반복해주어도 절대 쌍이 겹치지 않는다.

 

이제까지 우리는 j<=i인 보석 j에 대한 답만을 구해주었다. j>i인 보석에 대해서도 탐색을 해줄 필요가 있는데, 앞에서와는 다르게 함부로 이를 계산했다가는 같은 쌍을 2번 세줄 수 있기 때문에 추가적인 관찰이 필요한 시점이다.

 

(2) i<j일 때 물고기 j의 보석 쌍 집합에 포함되지 않는 물고기 i의 보석 쌍은 i번 종류의 보석을 최대한 많이 갖는 경우이며, 이때 j단계에서의 G[j][i]=G[i][i].

pf) i번 물고기가 i번 보석을 가지고 있는 가장 큰 물고기임을 되짚어보자. i번 물고기가 i번 보석을 최대 G[i][i]+1개까지 가질 수 있다. (본인이 갖고 있던 보석 i 포함) 따라서 만약 G[j][i]=G[i][i]이면 i번보석을 G[i][i]+1개 갖는 상황은 j에서 절대 일어날 수 없다.

 

이때 G[j][i]=G[i][i]+1이 되는 최소의 j는 i번 보석을 가지는 물고기위 최대 길이 L에 대해, 길이가 L/2이상이면서 i번 보석을 지니고 있는 물고기의 길이의 최솟값 L'의 2배이다. 즉, j=2L'. 이때 L'은 투포인터 혹은 이분탐색으로 빠르게 구할 수 있다.

 

이제 이것의 개수를 마저 세주도록 하자. 

답은 (1+G[1])*(1+G[2])*...*(1+G[i-1])*(1+G[i+1])*...*(1+G[j-1])-1이다. 이때 -1은 (1)에서 이미 세어준 경우인, '보석이 i 하나만 있는 경우'를 빼준 것이다.

 

우리는 (1+G[s])*...(1+G[e])꼴의 식을 빠르게 계산하기 위해 BIT를 사용할 것이다. 시간에 따라 G[*]가 1씩 변하기 때문에 업데이트 연산이 필요하기 때문. 따라서 시간복잡도는 O((K+F)logK). 

 

3. Islands

각 컴포넌트의 모양을 살펴보자. 컴포넌트의 크기를 C라 하면, 간선의 개수도 C이므로 그래프는 어떤 크기 2 이상의 사이클에 트리들이 붙어있는 모양이 될 것이다. 우리는 각각의 컴포넌트에서 최장경로를 구한 뒤 이를 전부 합쳐주면 되므로, 하나의 컴포넌트에서 최장 경로를 O(C)에 찾는 방법을 생각해볼 것이다.

최장경로가 생기는 다음의 두가지의 경우에 대해 각각 문제를 풀어주자.

 

(1) 트리의 지름

cycle위의 정점들에 대해 각각 실행해주면 된다. treedp를 써도 되고, 루트에서 가장 먼 정점 A를 구한뒤, A에서 가장 먼 정점 B를 구해 A와 B 사이의 거리를 구하는 것도 된다. 그러나 이 경우에서는 코딩의 편의를 위해 treedp를 쓰는 것을 추천한다. 위의 treedp과정으로 한번에 (2)번까지 처리할 수 있기 때문. 각 정점에는 그 서브트리의 높이를 저장해두고, 정점들을 합칠 때에 가장 긴 깊이 두개의 합이 가능한 답의 후보가 된다.

 

(2) 하나의 트리에서 시작하고 사이클의 일부를 따라간 뒤 다른 트리에서 끝나는 경로

사이클 위의 모든 정점들에 대해, 각각의 subtree내부에서 가장 깊은 정점의 깊이를 구해준다. 이때 (1)의 treedp를 쓰면 한번에 처리가 가능하다. cycle위의 정점들에 0(=M), 1, 2, .... ,M으로 번호를 매겨주었을 때, 위에서 처리한 값을 D[1], D[2], ..., D[M]=D[0] 이라고 부르겠다. 또한, S[i]를 cycle위에서 0->1->...->i의 경로의 길이라고 부르자. 그러면 i<j일때, i번 트리에서 시작하여 j번 트리에서 끝나는 최장경로는 다음의 식으로 계산할 수 있다. R(i, j)=max(S[j]-S[i]+D[j]+D[i], S[M]-S[j]+S[i]+D[i]+D[j])이고, 이를 각각 i, j에 대한 식으로 분리해주면 R(i, j)=max((D[i]-S[i])+(D[j]+S[j]), (D[i]+S[i])+(S[M]-S[j]+D[j]))이다. j가 고정되어 있을 때 우리가 필요한 값은 사실 max(D[i]-S[i])와 max(D[i]+S[i])이므로, j를 하나하나 늘려가면서 위의 두 값을 갱신해주면 O(M)에 모든 R(i, j)를 고려한 최장경로를 구할 수 있다.

 

결국 각 컴포넌트의 최장경로는 (1)의 답과, (2)의 답의 최댓값이며, 출력하는 값은 각 컴포넌트에 대해 계산한 최장경로의 합이다. 최종 시간복잡도는 O(∑C)=O(N).

 

+)풀면서 알게 된 점 : oj.uz에서 메모리를 최적화할때 inline을 붙이면 효과적이다. 그러나 백준에서는 택도 없다.