https://www.acmicpc.net/problem/12010 이해가 안가면 이 글과 참고해서 보면 좋다 : http://usaco.org/current/data/sol_landscape_platinum_open16.html여담으로 이 문제는 KOI 2005 소방차와 상당히 유사한 문제다. 같이 보면 좋을 듯 하다. http://koistudy.net/?mid=prob_page&NO=313 1. O((NK)^2)dirt의 개수만큼 위치를 저장해 놓은 수열을 펴보자. 예를 들어 3, 1, 5, 1과 같이 수열이 주어지면 0, 0, 0, 1, 2, 2, 2, 2, 2, 3과 같은 형태로 수열을 바꾸는 것이다.수열 A, B가 있을 때 진행하는 연산에 대해서 다시 생각해 보면* 1. 추가 -> 수열 B에 ..
https://www.acmicpc.net/problem/3319한동안 글을 한꺼번에 썼었는데 나눠 쓰는 게 여러모로 나을 듯 하다. 앞으로 그런 방향으로 바꿔나가려고 함.언제봐도 신기한 harbingers 문제를 다시 리뷰하려고 한다. O(N^2)dp[i] = Min(dp[j] + (depth(i) - depth(j)) * V[i]) + S[i] for all j = (ancestor of i) 이다. Special Cases : Line O(NlgN) 일직선에서 이 문제는 아주 유명한 컨벡스 헐 트릭이다. (depth(j), func(j)) 라는 형태의 일차함수가 순서대로 들어오고, V[i] 쿼리를 이진 탐색으로 처리해 주면 된다. 이해가 안가면 여기서 멈추고, http://dyngina.tistor..
Soap Time (CF 118E) http://codeforces.com/contest/185/problem/E 일단 45도 돌려서 chebyshev distance로 생각하고, 지하철역이 없을 때에 대한 corner case를 처리해주자. 먼저 minsub[i] = (i번 정점에서 가장 가까운 임의의 지하철역까지의 거리) 를 정의하고, 구한 후 시작하자. 시간 제한이 넉넉하기에 아무 방법이나 썼는데, 난 2d range tree를 짠 후 parametric search를 돌리는 방식으로 O(nlg^3n)에 해결하였다. 문제 해결에 있어서는 최댓값을 최소화하기 때문에 직관적으로 parametric search가 떠오른다. parametric search를 구현하는 것이 가장 어려운 부분이다. 일단 답이..
- Total
- Today
- Yesterday