コンテストでの時間切れや解けなかった過去問を振り返って供養していく
問題
Difficulty: 1824 (記事作成時点)
供養
解法
- $\max(A_{1}, \dots, A_{N}) = A_{\max}$ とする
- $A_{1}, \dots, A_{N}$ を $K$ 回の操作で $x$ の倍数にできるかを以下の方法で判定する
- $x \gt A_{\max}$ のとき
- $Nx - \sum A_{i} \le K$ ならば可能
- $x \le A_{\max}$ のとき
- $a_{i} \le A$ であるような $a_{i}$ の個数およびそれらの合計を累積和で求めておくと、$(k - 1)x \lt a_{i} \le kx$ であるような $a_{i}$ を $x$ の倍数にするための操作回数をまとめて求めることができる
- $a_{i} \le A$ であるような $a_{i}$ の個数の累積和を $C_{A}$、合計を $S_{A}$ とすると、$( C_{kx} - C_{ (k - 1)x } )kx - ( S_{kx} - S_{ (k - 1)x} ) $
- よって、$O(\lceil \frac{A_{\max}}{x} \rceil)$ で操作回数の総和を求めることができるので、それが $K$ 以下か判定
- $\lfloor \frac{K+\sum A_{i}}{N} \rfloor \gt A_{\max} $ ならばそれが最大値となる
- $x = 1, \dots, A_{\max}$ について上記の計算をすると、全体で $\sum \lceil \frac{A_{\max}}{x} \rceil = O(A_{\max} \log A_{\max})$ で計算可能
実装
計算量は $O(N + A_{\max} \log A_{\max})$
公式解説
躓いた点
- 累積和で計算時間の削減をする部分が思いつかなかった
