BOJ 13208 - 승현이와 승현이

문제 : https://www.acmicpc.net/problem/13208

전에는 못 풀었는데 드디어 풀었다~

$state[a][b]$ : 조승현13이 $a$에 있고 조승현16이 $b$에 있는 상태
를 정점으로 하고 $c[a] * c[b]$를 정점의 비용으로 가지는 그래프를 생각해보자. 우리가 해야 할 것은 $state[a][b]$에서 $state[b][a]$로 가기 위해서 지나가는 정점들의 비용의 최대값을 최소화 하는 것이다. 만약에 문제가 정점의 비용을 최소화하는게 아니라 간선의 비용을 최소화하는 문제였다면 MST를 만들어서 구할 수 있을 것 같았다. 비슷한 아이디어로 정점의 비용이 작은 것부터 큰 것 순으로 보면서 트리를 만들어보기로 했다. 과정은 대략 다음과 같다

1. 정점을 비용순으로 정렬하고 비용이 작은 것 부터 본다.
2. 현재 보고 있는 정점이 $u$라고 하자
3. $u$와 인접한 정점들을 본다. 인접한 정점은 $v$라고 하자.
4. 만약 $u$와 $v$가 다른 집합에 속하는데 $v$의 비용이 $u$의 비용보다 작거나 같다면 $u$와 $v$를 같은 집합으로 합친다. 그리고 간선$(u, v)$를 따로 저장한다.

위 과정을 반복해서 나오는 간선들을 모으면 트리가 된다. 또한 이 트리상의 경로로만 이동하면 문제에서 요구하는 답을 찾을 수 있다. 직관적으로 이해할 수 있으므로 증명은 생략한다.

이제 문제는 트리에서 두 정점을 연결하는 경로상에 있는 정점의 비용 중 최대값을 찾는 문제로 바뀐다. 이건 LCA를 이용하면 각 쿼리를 $O(lgN)$에 처리할 수 있다. 문제를 푸는 총 시간 복잡도는 시간 복잡도는 아마 $O(N(N+M)+QlgN)$이 될 것 같다.

(먼저 맞은 사람들 코드를 보니깐 더 빠른 방법이 있나 보다.)

코드 : http://ideone.com/eBn2sQ