BOJ 10014 - Traveling Saga Problem (D1)

사용 알고리즘

Centroid Decomposition

 

풀이

일단 기본 아이디어는 트리와 쿼리 5와 비슷하지만 반대의 기능을 가진 쿼리를 이용한다. 트리와 쿼리 5는 다음과 같은 두 가지 쿼리를 구현해야 한다.

• 1. 정점 집합에 i번 정점을 추가/삭제한다.
• 2. 집합에 포함된 정점들 중 임의의 정점 v와 가장 가까운 정점과의 거리를 구한다.

여기서 2번 쿼리를 다음과 같이 수정해서 이용한다.

• 2. 집합에 포함된 정점들 중 임의의 정점 v와 가장 먼 정점을 구한다.

비슷해 보이지만 가장 가까운 거리와는 다르게, 가장 먼 거리는 centroid tree 상에서 조상들을 보면서 올라갈 때 같은 서브트리에 속한 정점을 고려하면 거리를 제대로 구하지 못하기 때문에, 자신이 속한 서브트리를 제외하고 가장 먼 거리를 빠르게 찾을 수 있어야 하는데, 이게 골치 아프다. 트리와 쿼리 4와 비슷한 느낌이다.

 

하지만 이제 시작이다. 이를 구현했다고 치더라도, 모든 정점을 집합에 넣은 다음 방문한 정점 순서대로 빼는 방식은 상수가 커 TLE가 나기 딱 좋다. 하지만 잘 생각해보면, 어떤 정점에서 가장 먼 정점은 항상 리프 노드여야 하므로 리프 노드들만 집합에 존재하게 관리하는 방식으로 문제를 해결할 수 있다.

이 정도면 문제 풀이 자체는 거의 완성되었다고 할 수 있다. 하지만 진짜 문제는 최적화 부분이다. 이 문제의 제한 시간은 3초인데, 위 풀이는 O(Nlog^2N)이지만 상수가 많이 커서 3초 안에 돌기 힘들다. 그래서 먼저 구현을 최대한 BBST를 덜 쓰는 방향으로 해 주어야 한다. 또 그 외에 시간을 줄일 수 있는 거의 모든 부분을 줄여야 한다. 필자가 적용한 최적화 중 일부는 다음과 같다.

1. fastio(링크)

2. register 변수

3. inline, 비트연산 대체, 중복되는 연산 전처리

등등을 해주고 제출을 해주면 (3000+a)ms (0<=a<100) 정도로 추정되는 TLE를 받을 수 있다.

assert로 돌면서 어디까지 도는지 확인해봤는데, N=250000일 때 249999번 정점까지 출력하게 하면 TLE가 아니고, 250000번 정점을 출력하면 TLE였다(..)

 

 

심지어는 운빨로 BOJ 서버 성능이 잠깐 쾌적해지면 한번 1%를 넘어가기도 한다.

 

3%까지 간 모습

 

이런 짜증나는 상황을 참고 조금씩 최적화를 하면서 제출을 해주면 AC를 받을 수 있다.

2000ms가 넘는 제출이 많은데, 필자가 실행시간 꼴지이다.

 

다들 트라이 횟수가 많다는 점과 정답 비율(10%)을 감안할 때 대부분이 이 문제를 이짓거리를 하며 풀었을 것이라고 생각한다. (아니면 억울하다)

 

짜증나긴 해도 다이아 1로 올려놔서 이 문제가 첫 D1 문제가 되었다.

코드는 생략.