http://www.koistudy.net/?mid=prob_page&NO=2058 재밌는 문제.. 텔레포터를 타고 여기저기 옮겨나간다는 문제의 개념이 상당히 당황스러울 가능성이 높다. 막히지 않으려면 "그래프"라는 사실을 빠르게 파악해야 한다. 나뉘어진 선분 구간은 정점이고. 텔레포트는 간선이라는 것을 관찰하면 * 경로 간선의 개수를 최대화 * indegree와 outdegree는 모두 1이다 (시작 끝점 빼고) * 텔레포터의 설치는 두 정점 i, j의 나가는 간선의 교환이다 이 사실을 파악하면 문제가 상당히 깔끔해진다. 먼저 그래프의 성질을 관찰하자. * 컴포넌트 내의 indeg / outdeg가 모두 1이면 컴포넌트는 사이클을 이룬다. * 고로 그래프는 사이클 컴포넌트들의 집합이다.. 근데 시작 끝..
https://www.acmicpc.net/problem/3323 일전에 한번 멘붕이라고 언급한 적이 있었는데 (http://amugelab.tistory.com/entry/201573-2015723-problem-solving) 제대로 접근하면 아주 어렵지는 않다. 먼저 삼각형 쿼리를 뜯어보자. 한 점이 원점인 삼각형이면, 각도 범위 안에 있는 점들 중에서, 해당 선분 아래에 있는 점이 존재하는가? 를 묻는 문제가 됨을 알 수 있다.그러면 각도 범위를 무력화하면 어떨까..? 그러면 꽤 유명한 문제다. (https://www.acmicpc.net/problem/7057) 들어오는 점 집합을 Convex Hull만 남겨두고, 이진 탐색을 하면 풀 수 있다. 복잡한 설명은 생략.. 문제는 쿼리가 구간으로 들..
https://www.acmicpc.net/problem/2434http://koistudy.net/?mid=prob_page&NO=375 모든 점을 통괄하는 경로는 교차할 수 없기 때문에, 윗바닥과 아랫바닥을 먹는 두 선이 갈린다고 생각할 수 있다. 두 선의 상태는 그렇게 많지는 않아서, 이 "두 선"을 바탕으로 점화식을 세우는 것이 좋을 것이다. 나의 경우에는 다음과 같은 세개의 상태가 나왔다. * U[i] = i번 줄까지의 원소들을 다 봤고, i+1번째 줄의 위에서 1 - 2번째 원소에 발을 내린, 그 외에는 전혀 건들지 않은 상태 * M[i] = i번 줄까지의 원소들을 다 봤고, i+1번째 줄의 위에서 1 - 3번째 원소에 발을 내린, 그 외에는 전혀 건들지 않은 상태 * D[i] = i번 줄까지..
- Total
- Today
- Yesterday