알고스팟 ANNIETIBBER
애니 티버가 서로 봤을 때 좌우 관계가 반대인 쌍의 수를 세는 문제이다.
각도로 정렬하면 답이 되는 경우는, 정렬된 배열 상에서 애니가 기준으로 보는 별의 왼쪽에 있는 별이 티버 배열에선 오른쪽에 있는 경우이다. 이는 inversion의 수와 같다.
머지소트를 짜거나, 구간합을 계산할 수 있는 자료구조를 쓰면 된다.
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
댓글
댓글 쓰기