yukcoder No.2221 Set X 解説

問題へのリンク

\(\lfloor \frac{A_i}{X} \rfloor\ (1\leq i \leq N)\) の種類数の計算方法を考えます。

\(A_{i+1}-A_i < X\ (1\leq i \leq N-1)\) のとき、\(\lfloor \frac{A_{i+1}}{X} \rfloor - \lfloor \frac{A_i}{X} \rfloor\) は \(0\) か \(1\) であるため、\(1 \leq i \leq N\) の範囲で \(\lfloor \frac{A_i}{X} \rfloor\) は \(\lfloor \frac{A_1}{X} \rfloor\) 以上 \(\lfloor \frac{A_N}{X} \rfloor\) 以下の値をすべて取ります。よって \(\lfloor \frac{A_i}{X} \rfloor\ (1\leq i \leq N)\) の種類数は \(\lfloor \frac{A_N}{X} \rfloor - \lfloor \frac{A_1}{X} \rfloor + 1\) 種類です。

\(X \leq A_{i+1}-A_i\) のとき、\(\lfloor \frac{A_i}{X} \rfloor < \lfloor \frac{A_{i+1}}{X} \rfloor\) が成り立つので、そのような \(i\) で列を分離させると上記の場合に帰着できます。

以上をまとめると、 \(X \leq A_{i+1}-A_i\) が成り立つ \(i\) を \(i_1 < i_2 < \dots < i_k\) として、\(\lfloor \frac{A_i}{X} \rfloor\ (1\leq i \leq N)\) の種類数は

\((\lfloor \frac{A_{N}}{X} \rfloor - \lfloor \frac{A_{i_k+1}}{X} \rfloor+1)+ (\lfloor \frac{A_{i_k}}{X} \rfloor - \lfloor \frac{A_{i_{k-1}+1}}{X} \rfloor + 1) + \dots + (\lfloor \frac{A_{i_2}}{X} \rfloor - \lfloor \frac{A_{i_1+1}}{X} \rfloor + 1) + (\lfloor \frac{A_{i_1}}{X} \rfloor - \lfloor \frac{A_{1}}{X} \rfloor + 1)\)

という風に計算できます。

\(X\) の昇順に見ていけば \(i\) の管理は全体で \(O(N\log N)\) で行えます。\(f(X)\) について愚直に計算すると \(O(k)\) だけかかりますが、\((X+1) \times (k+1) \leq f(X)\) が成り立ち、\(f(X) < f(1)=2N\) であるような \(X\) だけ興味があるので、\(k+1 \leq \lfloor \frac{2N}{X+1} \rfloor\) が成り立つような \(X\ (1\leq X\leq 2N)\) に対してだけ計算すればいいです。これは \(O(N\log N)\) で行えます。

実装例（PyPy3）