구사과

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

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

http://codeforces.com/contest/650 A x같은거 + y같은거 - 둘다같은거 3분 AC B 문제를 읽다가 내가 제대로 읽은건지 긴가민가해서, 시간을 너무 낭비한 문제. (큰 차이는 없었지만..) 시작 점을 binary search하던지, 답을 binary search 하던지, two pointers를 쓰던지... 16분 AC C tourist가 10분 안에 풀기에, 적어도 코딩은 쉬운 문제이구나라고 생각했는데, 결국 코딩이 쉬운 방법은 찾지 못했다. 그런 사람들 보고 함부로 문제 평가하지 말아야.. ㅠㅠ. 약간의 WA끝에 pretest를 통과. 풀이도 썩 쉽지는 않다. 같은 행 - 열에 있는 점들간에 그래프스럽게 에지를 이었다 생각하고 dfs하는게 풀이. 꽤 까다로운 문제였고 그런..

http://www.codeforces.com/problemset/problem/449/D O(2^20 * N) cnt[i] = (i를 서브마스크로 가지고 있는 Aj의 수) 라고 정의하자. 즉 수열 A에서 (Aj & i == i) 인 원소의 수이다. 이건 O(2^20 * N)에 계산 가능하다.이제 답은 2 ^ cnt[0] 이.. 었으면 참 좋겠지만, 0이 아닌 다른 수를 서브마스크로 가지고 있는 Aj들이 존재하기 때문에 저럴 수는 없다. 고로 포함배제를 사용한다. 포함배제를 사용할때는, i의 비트의 수를 기준으로 포함 / 배제를 나눈다. i의 비트의 수가 홀수면 2 ^ cnt[i]를 빼주고, 아니면 2 ^ cnt[i]를 더해주는 식이다. O(2^20 * 20 + N)a[i] = (Aj == i인 j의 수..

http://oj.uz/problems/view/JOI14_constellation2삼각형 하나를 잡고 나머지 삼각형을 빠르게 세는..? 류의 방법으로 계속 시도를 해봤는데 진전이 별로 없었다. 실제 풀이는 굉장히 중요한 2개의 lemma에 의존하는데, * 1. 교차하지 않는 삼각형 쌍에 대해서, 두 삼각형을 완전히 분리시키는 직선이 항상 존재한다. * 2. 교차하지 않는 삼각형 쌍에 대해서, 삼각형 1의 점 - 삼각형 2의 점을 잇는 두 직선을 고려해 보자. (경우의 수는 9개). 이 중 두 삼각형을 완전히 분리시키는 직선이 항상 2개 존재한다. Lemma 1이 상당히 감명깊었다. 삼각형 쌍을 분리하는 법을 깔끔하게 정의한 것도 그렇고, (자명하지 않은) Lemma 2와 엮어서 실제로 문제를 깔끔하게 ..

A 솔직히 5분도 너무 오래 걸린것 같다..5분 pretest pass. AC+ : 결국 어떤 문자열 S, T가 있을 때 S를 적당히 rotate해서 T로 만들 수 있느냐를 묻는 문제였다. 계속반에서 비슷한 문제 (기하 문제였다) 를 KMP로 푸는 사람들이 꽤 있었는데, KMP에 숙달되었거나 라이브러리가 있는게 아닌 한, 시간 버리고 점수 와장창 까이기 딱 좋은 방법이다. 적당한 기준 원소를 아무거나 잡고 (난 std::min_element 를 사용했다.) 그쪽을 기준으로 rotate하는 것이 가장 좋은 방법이라고 생각. stl 떡칠시 아주 빠르게 짤 수 있다. 특히 std::rotate가 꿀. 난 문제를 너무 대충 생각해서 코딩 + 시간이 살짝 말린 채로 시작했고 그 부분이 아쉽다고 생각한다. (다행이..

https://www.acmicpc.net/problem/2795딱 봐도 NP-hard같은 문제를 N = 100을 주고 출제한걸 보니 당황하지 않을 수가 없었다. 일단 유일하게 생각해 볼수 있을 만한 접근법은 http://koistudy.net/?mid=prob_page&NO=369 와 같은 류의 바이토닉 기반 DP인거 같다. 한번 그 점을 생각해보고 어떠한 식으로 DP를 짜야지 최적 경로를 고려하는 점화관계를 이끌어낼 수 있는지 알아보자. 일단 생각을 쉽게 하기 위해서 1 -> 2로 가는 임의의 경로를 고정시키고, 그 경로상에서 2 -> 1로 오는 경로를 그려놓았다.#1 같은 경우에는 그냥 플로이드 한번에 풀릴 거고#2 같은 경우에는 위 링크건 문제를 풀어봤다면 그렇게 어렵지 않다. 다음과 같이 dp를..

Hill Walk (USACO 2013.03 Gold)https://www.acmicpc.net/problem/5835x좌표를 쭉 증가시키면서, 현재 f(x) 값으로 정렬된 선분들을 들고 다니면 쉽게 풀 수 있다. 이런걸 하는 데 가장 좋은 툴은 뭐니뭐니해도 BST. 선분이 교차할 일이 없기 때문에 한번 삽입 할 때 제대로 삽입하면 끝까지 문제가 생기지 않음을 알 수 있다. 저런 정렬된 선분들을 제대로 들고 다니려면 1. comparator를 재정의해야 하고, 2. comparator의 반환값이 가변적이라는 사실에 언어가 x랄을 하지 않아야 문제를 풀 수 있다는 점을 유념해야 한다. 1번은 http://amugelab.tistory.com/entry/STL-priority-queue-%ED%99%9C%E..