구사과

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축은 이 때문에 약간의 좌..

Problem : N개의 점이 주어졌을 때 가장 거리가 가까운 점 쌍을 출력하라. 거리는 유클리드 거리를 기준으로 한다.https://www.acmicpc.net/problem/2261 Solution : 모든 쌍을 보는 문제에서 자주 쓰는 기법인 분할 정복을 사용한다. 분할 정복에 대해서 대충 안다면, * Divide : Solve(s, e) 함수를 호출했을 때, Solve(s, m) / Solve(m+1, e) 로 두개의 집합 내에서의 모든 쌍을 본다.* Conquer : 한쪽이 왼쪽 집합 / 한쪽이 오른쪽 집합일 때 왼쪽 집합과 오른쪽 집합간의 Closest pair를 빠르게 찾는다. 한쪽 끝이 왼쪽 / 한쪽 끝이 오른쪽이니까 뭔가 빠르게 되지 않을까. 라는 기대와 함께 (?) 와 같은 메커니즘으로..