구사과

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

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..

이 라운드는 내가 치지는 않았다. 몇가지 이유가 있었는데 1) 시작할때 즈음 코포 서버가 난장판이어서 2) 문제가 mathy하다는 불안감이 계속 들어서 3) 내가 너무 졸려서... 정도. 일단 오늘 일어나서 문제를 봤는데 확실히 2번은 잘못된 가정이었다 ㅠㅠ 그냥 문제가 어렵지 않은 셋이었던듯, 볼걸 하는 후회가 계속 밀려오지만, 그냥 다음 시험을 위한 발판으로 삼자고 자기위안중... Div2 A. Kyoya and Photobookshttp://codeforces.com/problemset/problem/554/A사실 그냥 답은 25|S| + 26이다 (....) 하지만 안전이 제일이라 난 Brute force로 짬. STL string + STL set을 쓰면 굉장히 빠르게 코딩할 수 있다.cpp :..

[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초 안에 통과될 만큼 시간복잡도가 나올 듯 하다. 사실 ..

http://codeforces.com/blog/entry/18009?#comment-232968이번에 ALREADY HAVE DONE이라는 팀으로 참가해서 전체 62등, Secondary 9등으로 마무리지었다. 탑텐에 떴으니 만족함 ㅎㅎ그냥 문제 수기 쓰고 정리하려고 한다. 정리해보니 내가 이렇게 심하게 버스를 탔다는 것을 다시 한번 느낌 (...) A : 쉬운 그리디가 존재한다. 내가 짰고 금방 풀었다.B : 욕하는 문제인데 난 초기에 여기서 완전 말렸다 ㅠㅠ m^3개의 가능성이 존재하는데, 일단 이 중 m^2 쌍을 precomputing하고, 쿼리당 O(m) 번 brute forcing하면 딱 시간 안에 나오는 문제다. 되게 열심히 체크하고 깔끔히 짰는데 아주 기본적인 부분에서 틀리고 완전 말림. ..