구사과

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

http://wcipeg.com/problem/ccc14s2p3 문제에서 주어지는 명령들을 CNF 형태로 해석해보자, 1 -> 늑대인간, 0 -> 시민이다. D a b => a -> b A a b => a -> ~b CNF 형태가 유용한 점 중 하나는 그래프 이론적인 해석이 가능하다는 것이다. (예를 들어 2-SAT은 도달 가능성 == clause의 모순 여부라는 점을 활용한다.) 여기서 특히 주목할 점은 문제의 조건 대로라면 이렇게 주어진 명령을 그래프화 했을 때 트리 (사실은 포레스트) 형태의 모습이 생긴다는 것이다. 여기서는 늑대인간의 수가 K개인 경우의 수를 묻기 때문에, 이제 조건을 만족하는 경우의 수를 셀 때 트리 DP를 사용하면 된다. 트리 DP를 사용한다 하면 당장 rough하게 떠오르는 ..

This is my problem solving log during my IOI training camp.It will not cover all of my camp problem, I will just list some interesting ones. Since I'm lazy enough to install Korean IME in Ubuntu, this log will be written in English. Day 1Game Strategy (WF 2014)https://www.acmicpc.net/problem/10053think backward. Buffed Buffet (WF 2014) https://www.acmicpc.net/problem/10051Didn't have enough time..