본문 바로가기

전체 글110

Persistent Segment Tree 1. SPOJ 'COT - Count on a tree'2. SPOJ 'MKTHNUM - K-th Number'3. Codeforces Round #140 (Div. 1) Problem E. Noble Knight's Path 2016. 2. 25.
SRM 682 Div.1 300 : tonyjjw랑 나랑 푼 방법이 거의 같은데 뭔가 이상하다. 우선 중복간선은 존재하지 않는다고 입력 조건에 있음. 각각의 간선을 잘라보면서 트리의 지름을 구하듯이 어떤 점에서 가장 먼 점을 찾고 거기서 또 가장 먼 점을 찾음. 지름의 길이가 5 이상되면 답이 되는 체인이 존재한다고 했서 맞았음. O(n^2).tonyjjw를 통해서 ainu7님의 정해를 들으니 a-b-c-d-e가 있으면, a-b와 d-e를 전처리로 n^2에 구한다. 이후 b와 d 사이에 존재하는 c 후보들에 대해 a와 e랑 다른 걸 찾으면 된다고 한다. 전처리를 잘하면 전체 O(n^2)에 수행된다. 450 : 간선 하나(중복 간선은 간선 하나로 전처리) 달린 정점들 개수(C)를 카운팅하고 다음에 n-C-1 출력하니까 예제가 다 .. 2016. 2. 23.
SRM 679 Div.1 250 : 그리디하게 풀린다. 밑에서부터 올라오면서 누적하고 음수되면 버리면 됨. 900 : D(i, j) : i번 가방에서는 점수 k인 카드를 쓸 때에 다른 가방에서 점수 j인 카드를 써서 좋은 수가 되는 경우의 수라 정의하자.D(i, j) = Sigma[Count(i, k) * (isGood(j+k)=='Y')]그러면 i < j일 때에 ans(i, j) = Sigma[D(i, k) * Count(j, k)]. 2016. 2. 22.
SRM 681 Div.1 300 : 정점을 압축하고 Parametric Search 하면서 Maximum Flow 돌리면 됨. 구간을 나타내는 정점을 압축할 때 구간의 경계는 분리해서 압축해야함. 예를 들어서, [L(1), R(1)], [R(1)=L(2), R(2)], ... [R(k-1)=L(k) R(k)]는 [L(1), L(1)], (L(1), R(1)), [R(1), R(1)], (R(1)=L(2), R(2)), [R(2), R(2)] ... 이런식으로. 그리디 해법이 있다는데 생각해보아야함. 500 : 가운데부터 넓혀나가면 됨. 메모리 제한이 빡빡해서 배열 별도로 잡으면 안되고, left right 포인터 2개 잡아서 하면 됨. N^2 같아보이지만, (i, X(i)) 점들을 좌표평면에서 생각하면 언덕 모양들이 나올 때에 .. 2016. 2. 19.
Smallest Enclosing Circle/Sphere Problem 관련하여 내가 Codeforces에 올린 Blog article흔히 가장 먼 두 점의 거리를 2로 나누면 답이 되는 원 또는 구의 반지름이 될 거라 생각하지만, 원의 경우에서부터 다음과 같은 반례가 있다.Codeforces에 올린 글에 링크 걸어놓은 논문에 의하면 gradient descent 방법으로 최적해를 구할 수 있음이 밝혀져 있다.따라서 전체 점들에 대한 컨벡스 다각형의 내부의 한 점에서 가장 먼 점으로 계속 이동해 나가다보면(한 term에 이동하는 비율은 단조 감소해야함) 반지름이 최소인 구의 좌표를 알 수 있다.연습문제로는 내가 만든 BOJ 11930번 문제가 있다. 2016. 2. 17.

티스토리툴바