구사과

저번에 스타트링크에서 잠깐 강의했을 때 사용했던 자료입니다. 만든 시간이 길지 않아서 자료의 질이 그렇게 좋지는 못하네요. (발표 이후 수정은 없었습니다 ㅠ)일반적인 분할 정복의 사용 예를 떠올리면서, Centroid를 지나는 전체 경로를 한번에 처리하는 것이 도움이 되는 경우가 있는지, 그러한 문제는 어떤 것들이 있는지 생각해 보시는 게 도움이 될 것 같습니다. (사실 이거는 많이 풀어봐야 압니다 ㅋㅋ)추천 문제는 딱히 생각이 안나는데 난이도 순으로 적자면 http://codeforces.com/contest/321/problem/C https://www.acmicpc.net/problem/5820 http://codeforces.com/gym/100570/problem/Fhttp://codeforce..

.. 다 정리할 생각은 없다. 그냥 어젯밤에 풀었던 문제들 정리. 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라고 무시하고 있었다..