청린의 게임개발 (Hard)

1. 작업 횟수와 일수

최종 진행도를 $T$, 필요한 일수를 $m$이라 하자. 작업 $i$를 수행하는 횟수는 $c_i=(T-a_i)/b_i$로 정해진다. 다음 조건이 필요충분하다.

$$c_i\in\mathbb Z_{\ge0},\qquad \sum_{i=1}^N c_i=Km,\qquad \max_i c_i\le m.$$

필요성은 명백하다. 충분성을 보이기 위해 남은 일수가 $m>0$일 때 남은 횟수가 가장 큰 작업 $K$개를 선택하자. 양의 횟수를 가진 작업은 적어도 $K$개이고, 횟수가 $m$인 작업은 최대 $K$개이므로 모두 선택된다. 선택한 횟수를 $1$씩 줄이면 합은 이고 모든 횟수는 이하이다. 이를 반복하면 유효한 일정을 얻는다.

2. 최종 진행도의 범위

$C=10^{18}$, $H=\max_i a_i$, 라 하자. 진행도는 감소하지 않고 각 작업은 하루에 최대 한 번 수행되므로, 인 해는 반드시 를 만족한다. 문제의 보장에 따라 이 범위에서 인 해를 찾지 못하면 불가능하다. 만으로 가 보장되지는 않으므로 일수도 별도로 검사한다.

3. 일반화된 CRT

모든 $c_i$가 정수이려면 $T\equiv a_i\pmod{b_i}$여야 한다. 현재 합친 조건을 , 라 하자. 처음에는 이다. 새 조건에 를 대입하면 이다.

$g=\gcd(D,b_i)$가 $a_i-r$를 나누지 않으면 불가능하다. 그렇지 않으면 에 대하여

$$x\equiv\frac{a_i-r}{g}\left(\frac Dg\right)^{-1}\pmod q$$

로 $0\le x<q$를 구하고, $r\leftarrow r+Dx$, $D\leftarrow Dq$로 갱신한다. 이면 이다. 역원은 확장 유클리드 알고리즘으로 구한다.

병합 중 $D>U$가 되면 $[0,U]$에 가능한 값은 $r$뿐이다. 병합을 중단하고 전체 입력에 대해 $T=r$의 나머지 조건, 범위, 횟수의 합, 최대 횟수, 일수 제한을 직접 검사한다. 아직 병합하지 않은 조건도 반드시 검사해야 한다.

4. 일차식과 하한

모든 조건을 합친 뒤 $D\le U$라면 $T=r+Dt$로 놓는다. 다음 값은 모두 정수이다.

$$\alpha_i=\frac{r-a_i}{b_i},\quad\beta_i=\frac D{b_i},\quad A=\sum_i\alpha_i,\quad W=\sum_i\beta_i.$$

따라서 $c_i=\alpha_i+\beta_i t$, 이다. 이므로 가 증가하면 일수도 증가한다. 먼저 로 둔다.

$c_i\le m$을 정리하면 $(K\beta_i-W)t\le A-K\alpha_i$이다. 인 경우 하한

$$t\ge\left\lceil\frac{K\alpha_i-A}{W-K\beta_i}\right\rceil$$

을 얻으므로 이 값으로 $\ell$을 갱신한다. 나머지 작업은 지금 처리하지 않고 마지막 후보에서 검사한다. 음수에 대한 올림 나눗셈도 정확히 구현해야 한다.

5. 첫 번째 합동식 후보

총 횟수가 $K$의 배수여야 하므로 $Wt\equiv-A\pmod K$를 푼다. $g=\gcd(W,K)$가 를 나누지 않으면 불가능하다. 그렇지 않으면 양변을 로 나누고 역원을 구하여 , , 로 나타낸다. 이면 이다. 하한 이상의 첫 후보는

$$t_*=t_0+P\left\lceil\frac{\ell-t_0}{P}\right\rceil$$

이다. 먼저 $t_*\le\lfloor(U-r)/D\rfloor$인지 확인한다. 범위를 넘으면 곱셈을 수행하지 않고 불가능으로 처리한다. 범위 안이라면 $T=r+Dt_*$를 계산하고 원래 조건 전체를 직접 검사한다.

6. 후보 하나만 검사하는 이유

$K\beta_i<W$인 작업의 조건은 하한에 반영했다. $K\beta_i\ge W$인 작업에서는 가 감소하지 않으므로 첫 후보가 부등식을 위반하면 이후 후보도 모두 위반한다. 도 증가하므로 첫 후보에서 이면 뒤의 후보도 불가능하다. 따라서 첫 후보가 성공하면 최소 일수이고, 실패하면 해가 없다.

7. 정수 범위와 복잡도

$U\le10^{27}+10^9$이고 CRT는 $D\le U$일 때만 병합하므로, 새 주기는 $$이다. 역원과 곱하기 전에 나머지를 취한다. 일차식의 합과 하한 계산의 분자는 절댓값 이하로 충분히 제한된다. 후보는 범위를 확인한 뒤에만 와 곱하고, 일수는 에서 횟수를 다시 구해 계산한다. 따라서 이 구현의 모든 중간값은 부호 있는 비트 정수 범위 안에 있다. 제한 없이 최소공배수를 끝까지 구하거나, 범위 밖 후보에 곧바로 를 곱해서는 안 된다.

$B=\max_i b_i$라 하면 고정 폭 정수 연산을 기준으로 시간 복잡도는 $O(N\log B+\log K)$, 공간 복잡도는 이다.

8. 서브태스크 풀이

서브태스크 1에서는 $b_i=1$이다. $d_i=H-a_i$, 로 놓고 라 하면 와 를 얻는다. 은 처음부터 같은 경우만 가능하다. 나머지는 하한을 구한 뒤 의 나머지를 부터 까지 열거하여 에 해결한다.

서브태스크 2에서는 최종 진행도를 $H$부터 $100\,000$까지 직접 열거하고 필요충분조건을 검사한다. $D\le\operatorname{lcm}(1,2,3,4,5)=60$, , 이므로 위의 첫 후보는 이고, 가능한 최소 진행도는 미만이다. 따라서 이 열거 범위로 충분하다. 시간 복잡도는 이다. 서브태스크 3은 전체 풀이를 사용한다.

Solution written by GPT