3/16 problem solving

가끔씩 푼 문제를 간략하게 정리해보는 것도 괜찮을 거 같다. 아주 간략히.

 

반 나누기

 

있는 간선을 다 없애고, 없는 간선을 다 만들어보자. 그리고 문제를 다시 해석하면, '다른 반 학생들 사이에는 간선이 없어야 된다.'라고 할 수 있다. 그러면 답은 이 그래프에서의 컴포넌트 개수와 컴포넌트 크기들임을 알 수 있다. 하지만 간선이 O(N^2)개라 탐색을 하기 힘든데, 제외되는 간선을 넣어놓고 적절히 set과 upper_bound로 BFS 돌아주자. 시간복잡도는 O(ElogV).

 

Ridges and Valleys

 

먼저 컴포넌트 단위가 아닌 한 정점마다 생각해주자. 각 정점마다 그 정점보다 높은 정점과 접하지 않으면 ridge, 그 정점보다 낮은 정점과 접하지 않으면 valley 형태라 해주자. 같은 높이의 정점과만 접하면 둘 다일 것이다. 그리고 같은 높이의 정점들에 대해서 BFS를 돌아준다. 컴포넌트의 정점들이 모두 ridge면 ridge,모두 valley이면 valley,모두 ridge이자 valley이면 둘 다이다. 시간복잡도는 O(N^2)인데 8방향이라 상수가 조금 더 붙는다.

 

Megalopolis

 

HLD. 말이 더 필요한가? 시간복잡도는 O(Mlog^2N).

 

Weights.

 

일단  milligrammes를 물건, weights를 상자라 하겠다. 굳이 해석하기 귀찮아서 그렇게 생각하고 풀었다.

 

일단 답을 이분탐색한다. K개의 물건을 상자들에 넣으려 할 때,당연히 가장 가벼운 K개의 물건들을 뽑는 것이 최적이다. 그리고 K개의 물건들을 N개의 상자에 넣어야 되는데, '가장 무거운 물건부터', '가장 여유있는 상자'에 넣는 것이 최적이다. 증명은 모른다. 그저 감각으로 찍었을 뿐이다. 그러면 구현은 pq로 쉽게 해줄 수 있고, 시간복잡도는 O((N+M)log^2(N+M))이다.

 

참고로 다 POI 2006/2007 문제다. POI 문제가 고퀄이라 해서 좀 풀어볼까 한다.