【UR #31】决战库尔斯克 - 题目 - Universal Online Judge
長さ $N$ の数列 $A=(A_1,A_2,\dots,A_N)$ が与えられる。
$1 \le i,j \le N$ なる整数 $i,j$ を選択した際、 $\max(A_i,A_j) \ \ {\rm mod}\ \min(A_i,A_j)$ を最大化せよ。
$2 \le N \le 5 \times 10^5$
$1 \le A_i \le 10^{18}$
見た目(特に制約)ヤバい。でも可能らしい。
初手 sort unique する。この時最大値を $M $ として、
- $M/2$ 以下の要素を $low$
- $M/2$ を超える要素を $high$
として分割統治を考える。
- $high$ 同士
- $M/2 < x \le y \le M $ なる要素について $y \% x$ の最大値を検討しているので、 ($high$ の最大値) $\%$ ($high$ の最小値) $=$ ($high$ の最大値) $-$ ($high$ の最小値) だけ考えればよい。
- $low$ 同士
- 再帰的にこの分割統治をすればよい。
- $high$ と $low$ とのペア
- ここが難しい。
- $low$ の要素 $l$ を固定する。
- $l \le$ ($high$ の最大値) $-$ ($high$ の最小値) であれば、$l$ が最適ペアに絡むことはないので無視。
- そうでない場合、 $l >$ ($high$ の最大値) $-$ ($high$ の最小値) なので、 ($high$ の最大値)$/l$ と ($high$ の最小値)$/l$ の整数部の差は高々 $1$ である。
- よって、 ($high$ の最大値) $\% l$ と (商の整数部が切り替わる直前の $high$ の要素) $\% l$ だけ見ればよく、 $O(\log |high|)$ でできる。
これで全体が $O(N \log N \log \max A)$ となる。
提交记录 #761557 - Universal Online Judge
本番は(商が $2$ 以上の部分は扱いづらいことから)この分割統治には気づいたが、 $high,low$ ペアの部分が解けなくて無理やり枝刈りしたコードを投げてシステスを耐えた。ちょっと直せばちゃんと解けるんだなぁ
