SRM 678 Div1 500

N개의 행성의 좌표가 주어진다. 그리고 M개의 미사일이 있는데, 이 미사일은 행성을 공격하면 행성의 좌표가 (x, y) 라 할 때 (0, 0) ~ (x + T, y + T) 의 사각형에 있는 모든 행성을 없앤다. 문제는 M개의 미사일로 N개의 행성을 모두 파괴하기 위해 필요한 최소 T이다.

생각해보면 어떤 행성 a가 다른 행성 b의 x, y 좌표가 모두 이하라면 a 행성보다 b 행성을 쏘는게 무조건 이득이다. 이를 바탕으로 실제로 고려대상이 되는 행성만 추려낼 수 있다. (정렬 후 스택을 써서 추려냈다.) 추려내고 나면 답을 t로 가정했을 때, 가능한지 안한지를 O(N)으로 구할 수 있다. 만약 어떤 t에서 가능했으면 t보다 큰 값에 대해선 무조건 가능하니깐 파라매트릭 서치를 쓸 수 있다.

요약 : 고려해야 하는 행성만 추려낸 뒤, 파라매트릭 서치

https://community.topcoder.com/stat?c=problem_statement&pm=13373
 http://ideone.com/LNXnwt

댓글

댓글 쓰기

이 블로그의 인기 게시물

BOJ 11478 - 서로 다른 부분 문자열의 개수

길이 $N$인 문자열 $S$의 서로 다른 부분 문자열의 개수를 세는 문제이다. 방법 1) Suffix Array + LCP $O(NlgN)$에 해결할 수 있다. 다른 곳에서 많이 볼 수 있는 풀이이다. 방법 2) 트라이 $O(N^2)$에 해결할 수 있다. 트라이에 $S$의 ${N(N + 1)} \over 2$개 부분 문자열을 모두 넣으면 최종적으로 트라이에 존재하는 노드의 수 - 1(루트 제외)이 답이 된다. 방법 3) 해싱 $O(N^2lgN)$에 해결할 수 있다. $S$의 ${N(N + 1)} \over 2$개 부분 문자열을 해싱하면서 유니크한 해싱값들의 수를 세면 된다. 코드 (트라이) :  http://ideone.com/bugbDy 코드 (해싱) :  http://ideone.com/hkjw5n
계속 읽기

repeated squaring

https://www.acmicpc.net/problem/1533 최대 가중치 5인데 한 정점을 정점 다섯개로 치환하고 모든 간선의 가중치가 1인것처럼 만든다. 그런식으로 만든 인접행렬을 거듭제곱하면 답을 구할 수 있다. http://codeforces.com/problemset/problem/621/E
계속 읽기