순례의 시작

풀이

아래에서 $K = 8$이다.

서브태스크 1 (1점)

그냥 $\binom{N}{K}$가지 경우를 다 시도해보면 된다.

서브태스크 2 (10점)

$n$번째 답을 $m$으로 고정한 뒤 생각해 보자. $\frac{P_1 + ... + P_K}{W_1 + ... + W_K} \geq m$을 정리하면 $\displaystyle\sum_{i}^{K} P_i - m * W_i \geq 0$을 만족하는 조합이 있는지 확인하는 게 된다.

$n + 7$까지의 $i$에서 $P_i - m * W_i$가 가장 큰 $K$개를 고르는 게 최선임을 쉽게 알 수 있으며, 그 합이 0 이상이라면 답은 $m$ 이상이다. priority_queue를 사용해서 $O(N lg K)$에 상위 $K$개를 구할 수 있다.

$m$이 증가하면 합이 감소하기 때문에 이분탐색이 가능하고, 이분탐색을 하는 횟수라고 $T$라고 하면, $N$개의 $n$에 대해 이분탐색을 해주어서 $O(N^2T lg K)$에 문제를 해결할 수 있다.

이분탐색 및 출력을 할 때 실수오차에 주의하자.

개선

$n$이 증가함에 따라 가능한 조합이 늘어나므로, 답 역시 단조 증가함을 알 수 있고, 이를 활용해 분할정복이 가능하다.

$f(l, r, s, e) = l\ ..\ r$ 구간의 답을 구하는 함수라고 하자. (단, 구간에서 답은 $s\ ..\ e$ 범위에 속한다.)

이를 일반적인 DnC Opt처럼 $l\ ..\ r$을 반으로 쪼개도 되고, 나는 $s\ ..\ e$를 반씩 쪼개며 분할정복을 했다. 이렇게 할 경우 위 방법에 비해서는 상수가 조금 줄어들지만, 시간복잡도는 여전히 $O(N^2T lg K)$로 전혀 줄어들지 않았다...

하지만 $N = 1000$일 때 이 방법으로 80ms를 찍은 뒤, 세 배만 빠르게 하면 $N = 10000$일 때도 3초 안에 충분히 들겠다는 생각이 들었고, 정해를 떠올리겠단 마음은 바로 공중분해되어서 사라졌다! 이제 어떻게 해야 세 배 빠르게 할 수 있을지만 궁리하며 두뇌를 풀가동했다.

서브태스크 3 (100점)

커팅

잘 생각해 보면 중간 지점의 답을 구할 때 $l\ ..\ r$ 혹은 $s\ ..\ e$ 구간에서 절대 답이 될 수 없는 성물들이 있음을 알 수 있다. 이를 적절히 지워줌으로써 최악의 경우를 회피할 수 있고, 시간복잡도가 어떻게 되는진 모르겠지만 저격 데이터가 없어서 그런지 정해보다도 훨씬 빠르게 작동한다!!

이를 비롯해 몇 가지 수정을 거치자, 2등이 252ms인데 44ms라는 결과를 받았다. 근데 252ms 받은 코드도 봤더니 커팅인 것 같다 ㅋㅋ

커 팅 조 아!!