구사과

Network (ICPC Seoul Regional 2007)https://icpcarchive.ecs.baylor.edu/index.php?option=com_onlinejudge&Itemid=8&category=283&page=show_problem&problem=1903처음에 DP로 접근했다 시간을 많이 날렸다. (DP 풀이는 잘 모르겠다.) 대충 이런 그리디를 짜서 live archive AC를 먹였는데, 데이터를 믿을 수 없는 저지이기 때문에 (...) 반례가 있다 싶으면 지적해주길 바란다. * 리프 노드를 깊이가 큰 순으로 정렬해서 처리한다. * 처리중인 노드에서 거리 K 이하에 서버가 없으면 노드의 K번째 조상에 서버를 지어준다. 아니면 넘어간다. 복잡도는 O(N^2)이다. Superset ..

http://www.codeforces.com/contest/484/problem/E질의를 볼 때 모든 길이 w의 subsegment를 다 볼거라는 생각으로는 진전이 없다. 대신, 답을 정해놓는 식의 binary search를 유용하게 쓸 수 있다. binary search로 접근해보자. 질의의 답이 H[i]라고 가정했을 때, 구간 [l, r] 내에서 주어진 조건을 만족하려면, H[i] 이상의 원소들로만 이루어진 연속 최대 구간의 길이가 W 이상이어야 한다.즉 문제는 구간 [l, r] 내에서 H[i] 이상의 원소들로만 이루어진 연속 최대 구간의 길이를 구하는 것으로 정리되었다. 크게 두가지 방법이 있다. * 1. Persistent Segment Tree기본적으로 구간 [l, r] 내에서 연속 최대 구간..

https://www.acmicpc.net/problem/9482Solution 1 :원으로 생각하면 골치아프니 (x, y, z)를 중심으로 하는 2k 길이의 정육면체를 생각하고, 여기 안에 있는 점들을 일일히 순회한다. 순회를 할 수 있다고 치면 복잡도는 얼마일까? 답에 도움이 안되는 점들은 정육면체 - 구 영역에 존재할 것이다. 이러한 영역은 8개이며, 8개 영역 각각에 속하는 모든 점들은 서로의 거리가 K 이하이다. 고로 각 영역에 이러한 점들은 많아야 O(sqrt(ans))개. 순회만 할수 있으면 된다.순회를 하는 건.. z축 기준으로 스위핑을 하며, 스위핑 과정에서 세그트리 + std::set을 사용했다. std::set은 y축 기준 정렬, 세그트리는 x축 기준이고, x축은 이 때문에 약간의 좌..