Yukicoder No. 67, 68 よくある棒を切る問題

Yukicoder No. 67, 68 흔한 막대 자르기 문제

문제 링크 (1) No. 67

문제 링크 (2) No. 68

문제

유우키씨는 $N$ 개의 막대를 가지고 있고, $i$번째 막대의 길이는 $L_i$입니다.

막대는 (길이를 나누는 방향으로) 자유롭게 자를 수 있고, 연결하는 것은 불가능합니다.

유우키씨는 길이가 같은 막대를 $K$ 개 만들고 싶습니다.

만들 수 있는 $K$ 개 막대의 길이로 가능한 최댓값을 구하는 프로그램을 작성해주세요.

입력

입력 형식은 본문을 참고해주세요.

 

No. 67

$1 \le N \le 200000 = 2 \times 10^5$

$1 \le L_i \le 1000000000 = 10^9$

$1 \le K \le 1000000000 = 10^{10}$

 

No. 68

이 문제는, $K$의 값이 $Q$ 개 주어지고, 해당 $K$ 마다 답을 구해야 합니다.

$1 \le N \le 100000=10^5$

$1 \le L_i \le 1000000000 = 10^9$

$1 \le Q \le 100000 = 10^5$

$1 \le K_i \le 500000 = 5 \times 10^5$

출력

 

No. 67

만들 수 있는 길이의 최댓값을 $1$번째 줄에 출력해주세요.

 

No. 68

$i$번째 줄에는 만들 수 있는 $K_i$ 개 막대의 길이로 가능한 값을 출력해주세요.

 

절대, 혹은 상대오차가 $10^{-9}$ 이하인 경우 정답입니다.

마지막에 개행문자를 넣어주세요.

예제 설명

1. 길이가 $20$인 막대를 정확히 $2$등분 하면 길이가 $10$인 막대를 $3$개 만들 수 있습니다.
2. 길이가 $20$인 막대를 $3$등분 하고, 길이가 $10$인 막대를 $20/3$만큼 남기고 자르면, 길이가 $20/3$인 막대를 $4$개 만들 수 있습니다.

풀이

No. 67

길이가 $x$인 막대를 $K$개 만들 수 있는지 없는지를 구해봅시다.

길이가 $L$인 막대를 잘라 길이가 $x$인 막대를 만들 수 있는 개수는 최대 $\left \lfloor \dfrac{L}{x} \right \rfloor$ 개입니다.

$N$ 개의 막대를 전부 사용해서 길이가 $x$인 막대를 만들 수 있는 개수는 $\left \lfloor \dfrac{L_1}{x} \right \rfloor + \left \lfloor \dfrac{L_2}{x} \right \rfloor + \cdots + \left \lfloor \dfrac{L_N}{x} \right \rfloor$ 개 입니다.

우리는 $O(N)$의 시간으로, 길이가 $x$인 막대를 만들 수 있는지 없는지 여부를 구할 수 있습니다.

 

이제 이를 이용해서, 답을 구할 방법을 생각해 봅시다. 길이가 $x$인 막대를 $K$ 개 만들 수 있다면, 길이가 $x$ 이하인 막대도 $K$ 개 만들 수 있습니다. 만들 수 있는 최대 길이가 $X$라고 하면, 길이가 $X$ 이하인 막대는 전부 만들 수 있고, 길이가 $X$ 초과인 막대는 만들 수 없습니다(최대 길이이기 때문입니다.)

 

이를 이용해서, 답이 포함되어있는 구간을 좁혀나가는 방식으로, 문제를 해결할 수 있습니다.

답으로 가능한 구간이 $a$ 이상 $b$ 미만이라고 합시다. $\dfrac{a+b}{2}$를 만약에 만들 수 있다면, 답으로 가능한 구간은 $\dfrac{a+b}{2}$ 이상 $b$ 미만이 됩니다. 만들 수 없다면, 답으로 가능한 구간은 $a$ 이상 $\dfrac{a+b}{2}$ 미만이 됩니다.

양쪽 경우 모두 구간의 길이가 $b-a$에서 $\dfrac{b-a}{2}$ 로 줄기 때문에, 해당 구간을 오차 범위 이내로 좁히면, 답을 오차 범위 이내에서 구할 수 있습니다.

 

시간은 $O(N \log(L/\varepsilon))$에 문제를 해결할 수 있습니다.

 

코드: https://yukicoder.me/submissions/734016

 

참고:

해당 코드는 정확한 답을 구하는 것은 아니지만, 정확한 답으로 수렴하는 수열을 구한다고 할 수 있습니다.

$i$ 번째 구간을 $[a_i, b_i)$ 라고 했을 때, $a_1, b_1, a_2, b_2, \cdots$는 코시 수열입니다. 그렇기 때문에, 정확히 한 점으로 수렴하고, 이 수열의 극한이 원하는 정답 $X$ 입니다.

No. 68

답을 정해놓는 방식으로 문제를 해결할 경우, 시간이 $O(QN \log(L/\varepsilon))$정도가 걸리기 때문에, 문제를 해결하기에는 어려운 제한입니다.

우리는 다른 방식으로 답을 구해나갈 것입니다. $K_i$의 제한이 작다는 점에 주목해서, $1$부터 $K$까지 하나하나씩 답을 구해나갑시다.

막대의 길이 $x$가 감소함에 따라 만들 수 있는 막대의 개수 $K$는 증가하게 됩니다. 이 수가 바뀌기 위해서는, 어떤 $i$에 대해 $i$번째 막대가 만들 수 있는 막대의 개수가 증가해야합니다. 이는 $\left\lfloor \dfrac{L_i}{x} \right\rfloor$가 증가하는 시점이고, $\dfrac{L_i}{x}$가 정수 $k_i$일 때입니다.

바꿔 말하면, 정수 $k_i$에 대해 $x = \dfrac{L_i}{k_i}$일 때 답이 바뀌게 됩니다. 즉, $x$가 $\dfrac{L_i}{k_i}$ 초과였다가 $\dfrac{L_i}{k_i}$ 이하가 될 때, 답이 $1$ 증가하게 됩니다. 물론, 해당하는 $i$가 여러 개라면, $i$의 개수만큼 증가하게 됩니다.

결론적으로, 우리는 $x$를 증가시키는 지점인 $\dfrac{L_i}{k_i}$로 가능한 것들을 모두 모아서, 큰 것부터 $K$번째 수를 고르면, 해당 $x$에 대해 막대를 $K$ 개 만들 수 있습니다.

 

물론, 이를 실제로 구현하려고 하면 $k_i$로 모든 정수가 가능하고, 정수의 개수는 무한하다는 문제에 빠지게 됩니다.

이를 해결하기 위해서, 우리는 당연한 사실을 하나 이용 할 것인데, $\dfrac{L_i}{k_i}$가 $\dfrac{L_i}{k_i+1}$ 보다 크거나 같다는 것입니다. 즉, $\dfrac{L_i}{k_i}$를 선택하기 전에는 $\dfrac{L_i}{k_i+1}$가 절대로 선택되지 않습니다.

이를 이용해서, 이제까지 고른 $\dfrac{L_i}{k_i}$를 모두 저장해 놓고, 다음 후보로는 $\dfrac{L_i}{k_i+1}$들 중에서만 고르면 됩니다. 만약에 $\dfrac{L_i}{k_i+1}$를 골랐다면, $k_i$를 $1$ 증가시키고, 다음 수를 같은 방법으로 고르면 됩니다.

최댓값을 고르는 방법은 우선순위 큐를 사용하면 됩니다. 그래서 $K$ 이하의 모든 답을 $O(K \log N)$에 구할 수 있고, 시간복잡도는 $O(K \log N + Q)$ 입니다.