구사과

.. 다 정리할 생각은 없다. 그냥 어젯밤에 풀었던 문제들 정리. https://github.com/koosaga/olympiad/tree/master/POI 에서 ontak10_으로 시작하는 cpp들이 풀이이다. Highways https://www.acmicpc.net/problem/8476 결국 dfs traversal로 나타내면 2차원 평면상에 몇개의 점이 있는지를 세는 문제로 환원할 수 있다. 전형적인 2D Query 문제. main.edu.pl에서 실험해 봤을 때 O(qlg^2n)은 TLE가 났었음. O(n + (m + q)lgn)에 짜야 한다. 요 근래 2D Query는 거의 상식이 되어 가는 것 같다. 잘 해야 한다. Excursion https://www.acmicpc.net/proble..

https://sio2.mimuw.edu.pl/c/wiekuisty_ontak2015/dashboard/ http://zimpha.github.io/2015/09/23/ontak-2015-translation/ 풀 수 있는 거 다 풀어서 종결했습니다. 아인타가 paint 못푼다고 놀려서 올클 도전하기로 했습니다. 올클했습니다. 푼건 이 색깔로 표기합니다. 구현은 https://github.com/koosaga/olympiad/tree/master/POI 에서 ontak15_ 로 시작하는 파일들입니다. Day 1 cie 풀이 설명은 귀찮으니 생략. 요약하자면 왼쪽 오른쪽으로 슥슥 긁으면 풀리는데 구현은 조금 까다롭다. 굉장히 많이 틀렸었는데 이유를 알고 보니 0을 leading zero라고 무시하고 있었다..

ACM ICPC Daejeon Regional 2016에 다녀왔습니다. 당연하지만 고등학생이니 경기하러 간 건 아니고 그냥 놀러 갔습니다. 대학생이 아니라 처음에는 대회를 치르는 사람들이 정말 부러웠지만, 지금 다시 생각해보면 스트레스 안 받고 2층에서 편하게 팝콘뜯으면서 입풀이하고 중계하는게 더 꿀인거 같네요. 아는 얼굴들도 워낙 많았고 재밌는 일도 많아서 오랜만에 정말 즐거운 시간 보낼 수 있었습니다. 특히 zigui님의 코스프레가 정말 인상 깊었습니다. 대전 리저널에 새 역사를 쓰신... 총 12문제가 출제됐는데, 중계석에서 풀면서 느꼈던 점은 어렵고 재미있다는 점이었습니다. 생각에 조금 더 비중이 맞춰졌고, 재미있는 아이디어도 많았던 좋은 세트라고 생각했습니다. 물론 잘 풀었다는 건 아니고, 알고..

https://speakerdeck.com/wookayin/fast-fourier-transform-algorithmhttp://cubelover.tistory.com/12 내가 개념을 설명하기에는 위의 링크로도 충분한 것 같아서 따로 설명을 하지는 않겠다. 특히 맨 처음 인용한 ppt 슬라이드가 엄청나게 이해하기가 쉬우니 보면서 따라가는 것이 좋을 것이다. 다만 생각의 흐름 정도를 정리하자면 * 다항식을 표현하는 데 있어서는 sigma(ai * x^i) 형태의 coefficient representation과, {(x1, f(x1)), (x2, f(x2)), .. (xn, f(xn))} 형태의 point-value representation이 있다. lagrange interpolation theore..

https://www.acmicpc.net/problem/3419격자 그래프가 주어질 때, 갔던 정점을 다시 들리지 않는 조건으로 First와 Second가 번갈아 움직인다. 움직일 수 없는 사람이 질 때, 각각의 정점을 시작점으로 했을 때, 각각의 정점에서 누가 이기는지를 출력하면 된다.격자 그래프는 이분 그래프다. 정점을 두 집합으로 쪼개서, 현재 정점이 속한 집합을 A, 반대 집합을 B라고 하자. 이 문제의 답은 이분 그래프의 최대 매칭과 관련이 있다.설명을 돕기 위해, 먼저 매칭 크기 == |A| 인 경우를 생각해 보자. 이 때는 First가 A에서 매칭된 B의 정점으로만 움직여주면, 항상 이길 수 있다. B가 어떻게 움직이든간에, A 집합에 있는 정점으로 다시 가게 될 것이고, 그 정점은 매칭에..

ASC 1. Reactor Coolinghttp://codeforces.com/problemset/gymProblem/100199/B 아무 circulation이나 찾으면 되고, 일반적으로 이것은 그냥 아무것도 흘려주지 않으면서 (...) 해결할 수 있다.하지만 에지의 flow 량이 Fi, j  이를 해결하기 위해서는, 양변에 Li, j를 빼줘서 Fi, j 당연히 단순히 이것으로 되지는 않는데, 양변에 빼줬으니, 정점 j는 그 대신 Li, j만큼의 유량을 보장받아야 하고, 정점 i 역시 Li, j만큼의 유량을 흘려야만 한다.고로, source와 sink를 만들어줘서, 이 정점에서 그 유량을 흘려주면 된다. max flow의 합이 Sum(Li, j)가 된다면, 모든 유량이 보장받았고, 해가 존재한다.cpp..

유량 알고리즘과 테크닉들은 다른 분야에 비해서 자명하지 않고 어려운 증명들을 상당히 많이 사용한다고 느꼈다. 이러한 증명들을 알아둬야지만 상급 문제들을 풀 수 있다고 생각해서, 여러 중요한 정리들을 증명해 놓으려고 한다. 엄밀하게 잘 증명하려고 노력은 하고 있지만 잘 될지는 모르겠다. (지적 환영합니다) 정리 글하고 같이 보자. (정리에 없는 내용들도 있다.) 1) Edmonds-Karp Algorithm이 VE^2인 이유 Edmonds-Karp Algorithm이 VE^2인 이유를 증명하기 위해서는, 증가 경로를 많아야 VE번 찾는다는 것을 보이면 된다. BFS 한번이 O(E)이기 때문이다. 이 사실을 보이겠다. 정의 1. 간선의 capacity == 간선에 흐른 flow 인 간선을 포화 간선이라 정의..

BOJ SPOJ얼마 전 코포에 비슷한게 나와서 풀어본 문제. 집합 S가 주어졌을 때 XOR 값을 최대로 하는 부분집합의 XOR 값을 구하는 문제이다. 대부분의 경우에 2^maxbit - 1이 나올 거 같이 생겼지만, 어떠한 비트들이 다른 비트의 값에 종속적이기 때문에 실제로는 그렇지 않다는 것을 알 수 있다. 여기서 약간의 선형대수학 지식을 활용하자. 일단 주어진 수들을 modulo 2에서의 벡터로 생각할 수 있다. 선대에서 보통 이러한 경우가 나오면 row echelon form을 구해서 종속 관계를 추려내는데, 이것도 똑같이 하면 된다. 주어진 수로 이루어진 row echelon form을 구하는 방법은 다음과 같다. 숫자를 하나씩 하나씩 넣어가는데, 각 숫자에 대해서 가장 큰 비트부터 본다. 현재 ..

http://codeforces.com/contest/724 B (14분) N^6 짬. 이거 별로 안쉬웠다... 그냥 글러먹은듯 ㅠ D B를 풀고 친구 스탠딩을 봤을 때(=14분) 정우형이 AC를 받은 걸 확인했다. 그래서 잡았다. 그 때까지만 해도 내가 이걸 한시간 이상 잡을 줄은 몰랐다.. 문제를 처음에 보고 lexicographically라는 조건을 보고 내가 처음 한 생각은 "길이를 최소화해보는게 좋겠군!" 이었다. 대충 이 때부터 망한 듯 하다. 길이를 최소화한 상태에서 lexicographically smallest를 구했더니 예제가 안 나왔다. 앞에서부터 안 뽑힌 것중 가장 character가 작은 걸 뽑아가는 그리디를 생각했다. 세그먼트 트리를 하나 짰다. 예제 안나왔다. 또 하나 이상한 ..

일전에 Coder's High 2016에 전갈 그래프에 대한 문제를 출제한 적이 있었다. 문제 전갈 그래프에 대한 이론적 뒷배경에 대해서는 위키백과 참고. 개인적으로 꽤 애착이 가는 문제인데, 사실 저 문제를 general case에서 해결하는 방법은 오랫동안 모르고 있었다. 고민을 했는데 못 풀고 결국은 관련 자료를 봤다. 재미있는 알고리즘이여서 공유하려고 한다. 그래프의 모든 정점의 degree에 대해서 생각을 해보자. 가시의 degree는 1이고, 꼬리의 degree는 2이고, 몸통의 degree는 n-2이고, 나머지 정점의 degree는 1 ~ n-3이다. 이제 아무 정점이나 잡은 후, degree에 따라서 케이스를 나누자. d = 1, d = 2, d = n-2일 경우에는 몇가지 케이스를 해결하..