구사과

(Ali Bahjati suggested for English translation, so I added some translation below. Thanks for the suggestion!) Day1 여태까지 봤던 올림피아드 중 가장 힘들었던 거 같습니다. railroad / shortcut 콤보에 정신을 못 차리고 아무것도 하지 못한 채 멘탈붕괴... 대회 전에는 별 생각없이 들어갔다가 정말 말 그대로 박살나서 나왔습니다. 이렇게 박살난 건 저만 그런건 아닌듯.. 배점이 너무 이상한 탓에 성적에 큰 상관은 없었던 것이 다행이지만, 여러모로 아쉬움이 많이 남는 날이었습니다. This was the most painful contest that I’ve ever been. I wasn’t reall..

http://acm.hdu.edu.cn/showproblem.php?pid=5306 세 종류의 쿼리를 지원하는 자료구조를 설계하는 문제이다. O((N + Q)lgN)에 해야 한다. * 1. 구간 [L, R]에 a[i] = min(a[i], V) 대입 * 2. 구간 최댓값 * 3. 구간 합 보통 이러한 문제들은 세그먼트 트리에 익숙하면 쉽게 풀 수 있고, 실제로 2번 쿼리까지는 쉬운 문제지만, 이 문제는 3번 쿼리 때문에 굉장히 어려운 문제가 되었다.해법을 이해하기까지도 상당히 힘들었는데, 결론부터 말하자면 다음 네 값을 관리해줘야 한다 : 구간 합, 구간 최댓값, 구간에서 최댓값이 자신의 값인 원소의 수, 구간 두번째 최댓값. 두번째 최댓값은 최댓값보다 작아야만 한다. 먼저 이 값들을 제대로 관리했다면,..

그래프 이론에서 Dynamic Connectivity Problem은, * 1. 정점 u, v를 잇는 간선 추가 * 2. 정점 u, v를 잇는 간선 제거 (이미 있다고 치자.) * 3. 그래프 상에서 두 정점이 연결되어 있는지 체크와 같은 질의가 주어졌을 때, 이러한 질의를 빠르게 응답하는 방법을 찾는 문제이다. O(Q|V|) 나 O(Q|E|) 정도에는, 기본적인 그래프 탐색 알고리즘으로도 아주 쉽게 풀수 있지만, 더 나은 복잡도를 내기는 쉽지 않은 문제이다. 2번 쿼리가 없다면 union-find data structure (링크) 를 사용해서 쉽게 풀 수 있지만, 더 복잡한 질의가 들어왔을 때는 쉬운 풀이가 존재치 않는다. 일반적인 경우 이 문제의 해법은 매우 어려워 보인다 (링크). 하지만, 오프라..