チョンリンのゲーム開発 (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. 一般化された中国剰余定理

すべての $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-W)t$ は減少しないため、最初の候補が不等式を満たさなければ、それ以降も満たさない。日数 も増加するので、最初の候補で なら後の候補も不可能である。したがって、最初の候補が成功すれば最適であり、失敗すれば解はない。

7. 整数の範囲と計算量

$U\le10^{27}+10^9$ であり、$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