2018 KAKAO CODE FESTIVAL 예선

A번부터 E번까지 해결하였고, F번은 해결하지 못했다.
대회 중에 내가 정답 판정 받은 코드는 여기서 볼 수 있다.
아래는 간략한 풀이 및 스포일러이다.

A. 상금 헌터
간단한 구현 문제.
등수가 0일 때에 주의한다.

B. 인형들
N이 500이하이므로 평균과 표준편차 정의에 의해 단순히 계산하면 된다.
자료형 오버플로우에 주의한다.

C. 숏코딩
== 연산과 != 연산에 대해 구분하여 생각할 수 있다.
== 연산의 경우, 연결 관계를 그래프로 표현하였을 때에 각 component가 독립적인 문제이다.
이 component에서 길이가 가장 짧은 하나의 노드와 다른 노드의 연결 관계를 모두 표현하는 것이 최적임을 알 수 있다.
!= 연산의 경우에 대해서는 서로 다른 컴포넌트 간의 관계만 표현해주는 것이 최적이다.
주어진 식이 항상 참이거나 거짓일 수 밖에 없는 경우에 대해 주의하면 된다.

D. 부스터
첫 번째로 관찰할 수 있는 사실은 부스터를 사용하고 나서 직교하게 이동하는 것이 연료 사용량을 최소화한다는 것이다.
따라서 2차원 평면 상의 각 점들을 X축에 정사영하고, Y축에 정사영하여 생각해보면, 사용 가능한 최대 연료량이 증가함에 따라 서로 오갈 수 있는 점들의 집합이 점차 union 되어간다. 이 때에 인접한 점 간의 거리를 힙 또는 우선 순위 큐에 담아두고 작은 것부터 차례로 꺼내어 처리하면, 최대 연료량 오름차순으로 정렬된 쿼리에 대해 순차적으로 답할 수 있다.

E. 음악추천
병렬 이분 탐색(parallel binary search)로 해결할 수 있다.
각각의 가수(singer)에 대해 몇 번째 쿼리까지 수행하면 가중치 평균이 J를 넘는지에 대해 이분 탐색을 한다.
이분 탐색을 수행하게 되는 중간값에 대해 오름차순 정렬하고 난 후, 트리를 탐색하면서 각 노드를 루트로 하는 서브트리의 가수들은 얼마의 가중치가 더해지게 되는지를 fenwick tree로 빠르게 계산할 수 있다.

F. 프로도의 100일 준비
분할정복으로 접근하였으나 남은 시간 내에 해결하지 못했다.
doju님께서 Dynamic Convex Hull로 해결할 수 있다고 하셨다.