구사과

https://www.acmicpc.net/problem/3323 일전에 한번 멘붕이라고 언급한 적이 있었는데 (http://amugelab.tistory.com/entry/201573-2015723-problem-solving) 제대로 접근하면 아주 어렵지는 않다. 먼저 삼각형 쿼리를 뜯어보자. 한 점이 원점인 삼각형이면, 각도 범위 안에 있는 점들 중에서, 해당 선분 아래에 있는 점이 존재하는가? 를 묻는 문제가 됨을 알 수 있다.그러면 각도 범위를 무력화하면 어떨까..? 그러면 꽤 유명한 문제다. (https://www.acmicpc.net/problem/7057) 들어오는 점 집합을 Convex Hull만 남겨두고, 이진 탐색을 하면 풀 수 있다. 복잡한 설명은 생략.. 문제는 쿼리가 구간으로 들..

https://www.acmicpc.net/problem/2434http://koistudy.net/?mid=prob_page&NO=375 모든 점을 통괄하는 경로는 교차할 수 없기 때문에, 윗바닥과 아랫바닥을 먹는 두 선이 갈린다고 생각할 수 있다. 두 선의 상태는 그렇게 많지는 않아서, 이 "두 선"을 바탕으로 점화식을 세우는 것이 좋을 것이다. 나의 경우에는 다음과 같은 세개의 상태가 나왔다. * U[i] = i번 줄까지의 원소들을 다 봤고, i+1번째 줄의 위에서 1 - 2번째 원소에 발을 내린, 그 외에는 전혀 건들지 않은 상태 * M[i] = i번 줄까지의 원소들을 다 봤고, i+1번째 줄의 위에서 1 - 3번째 원소에 발을 내린, 그 외에는 전혀 건들지 않은 상태 * D[i] = i번 줄까지..

https://www.acmicpc.net/problem/2584 1. O(N^3)dp[node][k][state] 라는 N^2 점화식을 생각해보면 서브 트리에 대해서 http://amugelab.tistory.com/entry/CCC14-Stage-2-Werewolf 의 해법으로 풀 수 있다. 복잡도는 O(N^3). 2. O(N^2)이 문제에서 두 DP값은 DP[i] = min(DP1[j] + DP2[i-j]) 라는 방식으로 합쳐지는데, 내가 아는 한에서는 이는 O(N^2)보다 빠르게 계산할 수 없다. 아마 실제로도 계산할 수 없을 것이다. 증명은 못하지만...고로, 뭔가 다른 걸 궁리해야 한다 생각하기 쉬운데 답은 의외로 가까이에 있다. 두 서브트리 사이즈가 A, B이고 여기서 DP배열을 O(AB)에..

https://www.acmicpc.net/blog/view/10

nCr = n! / (n-r)! * r! 일 때, nCr mod prime을 빠르게 계산하는 방법에 대해서 얘기하려 한다. nCr 한 쿼리는 O(1)에 처리되어야 한다고 가정한다. (즉 전처리 한번 한 이후 nCr을 하나 계산하는데 O(1)) 1. O(n^2)위에 저 식을 그냥 구현만 해도 O(n) 인데..! 하지만 컴퓨터의 메모리는 한정되어 있으니 수를 그대로 들고 갈 수는 없고, mod p는 나눗셈을 하기 썩 좋은 상황은 아니다.그래서, nCr = (n-1)C(r-1) + (n-1)Cr 이라는 점화식(파스칼의 삼각형)을 사용해서 n^2에 계산하는 게 잘 알려져 있다. N^2 크기의 배열을 잡고 서서히 계산해 나가는 것이다. 이 방법은 나눗셈을 완전히 우회하는 방법으로써 사실 여러모로 제일 안정적인 방..

http://evenharder.tistory.com/

http://www.spoj.com/problems/IE3쿼리당 Sqrt(N)lgN에 풀 수 있다. N 이하의 Square 수가 모두 Sqrt(N)개 있을 텐데, 이걸 단순히 포함배제로 하면 - * 2^2의 배수 더해주고 - * 3^2의 배수 더해주고 - * 6^2의 배수 빼주고 - * 4^2의 배수는 냅두고 - * 5^2의 배수 더해주고 - ( ..... ) 말도 안되는 시간 복잡도가 나오겠지만 이 때를 위해서 뫼비우스 함수라는 것이 존재한다. 뫼비우스 함수 f(n)은 : * f(n)이 제곱수로 나눠지면 0 * f(n)의 소인수 수가 홀수면 -1 * 아니면 1 으로 정의되는데 이걸 쓰면 저걸 어떻게 해주면 되나면 * f(6) * 6^2의 배수 더하고 * f(5) * 5^2의 배수 더하고 (....) 이..

http://wcipeg.com/problem/ioi0423 O(M^2) 관찰해야 할것은 모든 엠포디아들이 Disjoint하다는 것이다. 완전한 포함 관계는 당연히 없을 거고 겹치는 것에 대해서 얘기하자면, 두 framed interval이 [a, b] / [c, d] 로 겹쳐있다면 (a < c < b < d), [a, b] / [b, c] / [c, d] 구간 모두 framed interval이다. 고로 [a, b]와 [c, d]는 엠포디아가 될 수 없다. 이러면 구간의 시작점을 감소시키면서 루프를 돌고, 해당 시작점에서의 empodia가 있으면, 끝점의 범위를 감소시켜나가면서 계속... 하는 M^2 알고리즘을 만들 수 있다. 조금 더 자세히 하자면, (i, j) 쌍을 찾을 때 i = N-1에서 감소 ..

Floyd-Warshall로 최단 경로의 개수를 셀 수가 있는데. 3중 포문을 돌면서 거리와 count를 같이 갖고 있으면서 돌리면 된다. 예를 들어 현재 Dist(j, k) > Dist(j, i) + Dist(i, k) 라서 업데이트 된다면,Count(j, k) = Count(j, i) * Count(i, k) 이고,Dist(j, k) == Dist(j, i) + Dist(i, k) 라면Count(j, k) += Count(j, i) * Count(i, k) 이다. 초기 조건은 주어지는 에지들이면 Count 1 아니면 0 이런 식이면 된다. 신기함 ㅋㅋ 연습 문제 : http://wcipeg.com/problem/noi07p1

http://wcipeg.com/problem/ccc12s2p6 먼저 아군과 적군은 cost 1, cost -1의 점으로 생각할 수 있으니 같이 생각하자.문제는 (0,0) 점에서 시작해서 돌아오는 polygon을 만들고 안에 들어있는 cost의 합을 최대화 하는 문제이다. 세 점이 한 직선에 없어서 깔끔한 문제. * N 0인 체인을 쭉 만드는 문제로 생각하자.Sum[j][k] = (A[j] - A[k] - 원점 안에 들어있는 점의 가중치합) 라고 하면 이제 동적 계획법을 돌리는데 DP[i][j] = Max(j < k) DP[j][k] + Sum[j][k] + A[j].cost 라고 돌리면 되고Sum과 DP 배열을 N^3에 계산하면 됨. * N