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..
[5/13 초본, 5/27 L 추가, 5/28 M 추가, 6/22 I,J 추가, 6/23 N,T 추가] 흔한 DP 컨테스트라고 말은 하지만, 어렵다.http://tdpc.contest.atcoder.jp/ ASubset Sum이라는 유명한 문제로, 풀이 역시 유명하다. 개행 문자를 넣어야만 AC가 되니 유의.cpp : http://codepad.org/nKJbfaBR Cwin[player][i] 를 i번째 라운드까지 진행되었을 때 player의 승률이라 정의하자. 동적 테이블을 채울 때, 각 플레이어가 i-1번째 라운드를 통과하고 본인과 대전할 확률을 구할 수 있으며, 싸워서 이길 확률은 식으로 주어져 있다. 이를 통해서 테이블을 채울 수 있으며 1초 안에 통과될 만큼 시간복잡도가 나올 듯 하다. 사실 ..
https://www.acmicpc.net/problem/1200 Naive하게 하면 (n-1)Cr * (m-1)Cs 정도의 시간에 풀 수 있으며 당연히 TLE가 난다. ( 상한이 O(2^(n+m) 이다.) 그럼에도 n과 m이 작은 편이라 지수를 하나 정도만 날려도 될 거 같은 범위이다.. 실제로 그렇고. 일단 한가지 축으로 배열을 미리 잘라놓고 생각을 하면, 이는 여러개의 1차원 배열을 자르는 문제로 환원이 된다. 배열은 (s+1)개 나올 것이며, 이를 구간 [1,a1] , [a1+1,a2] ... [as+1,n] 으로 자르는 것이라고 생각하면, Max(1
https://www.acmicpc.net/problem/10454 Observation 1. 모든 정점을 포함하는 최소의 직사각형을 가정하자. 이를 세 정사각형으로 채울 때, 세 정사각형 중 하나는 그 직사각형의 모서리를 모서리로 가지고 있다.-> 그렇지 않게 정사각형을 열심히 그려보면 (...) 알 수 있다. 케이스를 많이 나누는 식으로 증명이 되지 않을까.. 싶다. Observation 2. 모든 정점을 포함하는 최소의 직사각형을 가정하자. 이를 두 정사각형으로 채울 때, 두 정사각형 중 하나는 그 직사각형의 모서리를 모서리로 가지고 있다.-> 역시 그렇지 않게 정사각형을 열심히 그려보면 (...) 알 수 있다. Observation 3. X가 3SQ-sufficient 일때 X+1은 3SQ-suf..
- Total
- Today
- Yesterday