problem solving 2016.01.30

프리스비 (USACO Gold 2014.12)

https://www.acmicpc.net/problem/10649

N이 작은 문제다. 

1) 비트 DP를 한다. dp(S) = 현재 집합의 추가 가능한 스택 양 이라 정의하면, Min(dp(S\j), Pj - Sum(S\j)) 중 최대인 j를 고르면 된다. 이후 모든 부분집합 S 중에 높이 합이 H 이상인 애들에 대해서 최댓값을 고른다.

2) 그리디를 한다. 집합이 고정되어 있을때, P + W 순으로 정렬한 후 구한 Min(P + W - S) 값이 항상 가능한 순열 중 최대를 낼 수 있다는 것을 증명할 수 있다. 고로 초기에 P+W 순으로 정렬후 모든 집합에 대해서 시뮬레이션하면 된다. 이런걸 그리디로 할 때는, deadline first라는 걸 기억해두면 편한거 같다.

Like (BOJ 3204)

https://www.acmicpc.net/problem/3204

모든 정점의 degree가 짝수일 때는, 오일러 회로를 찾은 후 그에 따라서 간선을 맞춰주면 답을 구할 수 있다.

홀수 차수 정점이 있을 때는, 단순히 홀수 차수 정점을 묶어주는 dummy node를 만들어 준다. dummy node가 1개밖에 없으니 |indegree - outdegree|도 많아야 그정도일 테고, 고로 간선의 방향을 그러한 형태로 그려주면 답을 구할 수 있다.

말하고 나면 참 자명한데 떠올리기는 생각보다 어렵다 ㅠㅠ

라디오 전송 (BOJ 3356)

https://www.acmicpc.net/problem/3356

failure function을 구하면, 답이 n - fail[n]임을 알 수 있다.

Horizontally Visible Segments (BOJ 3468, CERC 2001)

https://www.acmicpc.net/problem/3468

연결 관계의 수, 즉 간선 개수가 많아야 O(N)이다. 난 O(NlgN) sweep line 알고리즘을 고민하다가 이 사실을 깨달았는데, 평면 그래프를 생각해보면 이해가 조금 더 쉬울 거 같다. 아무튼 삼각형 구하는건 O(NM)= N^2에 되고, O(N^2)에 sweep line algorithm으로 간선을 구하면 된다. 괜히 O(NlgN)을 짜다가 말렸다 ㅠㅠ..

카드 배열 (BOJ 2534, KOI 2012 지역본선)

https://www.acmicpc.net/problem/2534

사전순 최소 위상정렬을 찾는 것에 대한 문제이다. queue로 위상정렬하는 것 대신 priority_queue를 사용해서 위상정렬을 하면 될거 같다는 생각이 들 것이다.

Ci > Cj일 때 i -> j 간선이 이어져 있다고 생각을 하고, 값을 최소로 하는 카드 배열을 찾는다고 하면, 현재 pq에서 가능한 원소중 인덱스가 최소인 것을 찾고, 거기다가 가장 큰 값을 계속 greedy하게 대입해주면서 문제를 풀면 된다. 일반적으로 생각하는 것과 반대 방향이라 많이 헤맸다 ㅠㅠ

Phone Cell (BOJ 3437, CERC 2007)

https://www.acmicpc.net/problem/3437

답이 될 수 있는 송신기의 위치는 각 점을 중심으로 하는 크기 R의 원의 교집합일 것이다. 고로 문제를 각 점을 중심으로 하는 크기 R의 원이 주어졌을 때, 최대 몇개의 원이 겹치는지를 구하는 문제로 바꿀 수 있다.

만약, 그러한 영역이 존재한다면, 그 영역은 몇개의 호들로 둘러싸여진 영역일 것이다. 즉, 그러한 영역 중 한 점은 어떠한 원의 호 상에 존재한다. 고로, 영역을 호의 구간으로 표현해도 상관이 없다.

이 점을 알면 다음과 같은 알고리즘을 사용할 수 있다. N개의 원을 각각 잡은 후, 각 원에 대해서 또 N개의 원을 본 후, 두 원이 겹치는 부분을 호의 구간으로 표시해준다. 호의 구간들을 원주 상에 나열했을 때, 어떤 원호에 K개의 구간이 쌓였다면 K+1개의 점을 포함하는 원의 중심이 그 원호상에 있을 수 있다. 고로 가장 많이 호가 쌓인 곳이 어디인지를 찍어주면 된다. 복잡도는 O(N^2lgN).

여담으로, 이 알고리즘에 이진 탐색을 더하면 O(N^2lgN * lg(1/e)) 에 Smallest Enclosing Circle을 풀 수 있다. 시간이 좀 느려서 컨벡스 헐로 커팅해줘야 함 (....) (https://www.acmicpc.net/problem/2626)