구사과

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

David Byrne - Help Me Somebody (My Life at the Bush of Ghosts, 1981) The Who at Rockpalast (1981. 03. 28) The Who - You Better You Bet (Face Dances, 1981) Pavement - Stereo (Brighten the Corners, 1997) Pavement - Gold Soundz (Crooked Rain, Crooked Rain, 1994)

페북에 굴러다니던건데http://tncks0121.tistory.com/ 블로그 주인장 분의 "강력한" 건의로 인해 블로그에도 올리게 되었다.덧붙이고 싶은 내용들을 조금 추가했다. 문제 후기 말고 대회 후기도 써야 하는데 안썼다.아마 안쓸듯. 나새끼.. boxes 제일 쉬워보였고 실제로도 쉬운 문제였습니다. 일단 O(nk) dp를 빠르게 코딩하고, 그리디 전략과 섞어서 O(n)에 해결했습니다. n이 천만으로 매우 큰데 나름 시사하는 바가 있다고 생각합니다. (소스 : http://oj.uz/submission/16536) scales 빠르게 머지소트 55점 풀이를 코딩하고 3번으로 넘어갔습니다. 71점 풀이는 처음반때 decision tree 배울때 생각했던 풀이로 애석하게도 바로 떠오르진 않았습니다 (..

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/

(Summerteeth, 1999)

http://news.naver.com/main/read.nhn?mode=LSD&mid=sec&oid=025&aid=0002534087&sid1=001 서울대는 몇 년 전 지원자들의 생활기록부에 올림피아드 관련 수상 실적이 지워지지 않았다고 해서 교육부로부터 경고를 받았다고 한다. 교육부의 재정 지원을 받는 서울대로서는 이런 통제에서 벗어나기 힘들 것이다. 고교 3년을 온통 컴퓨터 프로그래밍에 미쳐 생활한 학생의 생활기록부에 이걸 제외하고 무엇을 적으란 말인가. 입시전형을 다양화해 다양한 자질을 가진 학생들을 선발하도록 하겠다더니 이런 인재들의 진입은 원천적으로 봉쇄하고 있다. 대통령이 “창의성을 갖춘 인재가 국가 경쟁력을 좌우하는 시대를 살아가고 있다” “학생의 꿈과 끼를 키우는 교육을 해야 한다”고 ..

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에서 감소 ..