I - K-th Largest Triplet 解説
by 
Kiri8128
O(K^(2/3) log N logM) 解法
\(A_i,\ B_i,\ C_i \leq M\) （ \(= 10^9\) ）として、 \(O(K^{2/3} \cdot \log N \cdot \log M) \) 解法を紹介します。
答えに関する二分探索を考えることで、 \(x\) を固定したときに \(A_{i}B_{j} + B_{j}C_{k} + C_{k}A_{i} \geq x\) となる \((i, j, k)\) の組が \(K\) 個以上あるかどうかを判定する問題に帰着できます。
以下、この判定問題を考えます。
添え字 \(i, j, k\) をすべて調べると正しい答えが得られますが、計算回数が多くなる可能性があるのでうまく枝刈りをしたいです。 \(i, j, k\) を昇順に並べ替えたものを \(i' \leq j' \leq k'\) とします。 このとき \({i'} ^3 \leq K\) かつ \(i' \cdot {j'}^2 \leq K\) が成立する範囲のみを調べても結果が変わらないことが分かります。
証明
公式解説1 で書かれているとおり、添え字について単調性があることに注意します。$r=\lfloor K^{1/3} \rfloor$ とします。ここで $(r + 1)^3 > K$ に注意します。また $f(i, j, k) = A_{i}B_{j} + B_{j}C_{k} + C_{k}A_{i}$ とします。
前者の条件（ ${i'} ^3 \leq K$ ）は、 「 $i > r$ かつ $j > r$ かつ $k > r$ の範囲を調べなくて良い」と等価です。この範囲の最小のものは $f(r+1, r+1, r+1)$ です。 この値は、 $i, j, k$ を $i \leq r + 1, j \leq r + 1, k \leq r + 1$ の範囲を動かしたときの最小値なので、これらを除いても上位 $K$ 個には影響がないことが分かります。
後者についても同様に示せます。
すなわち、 \(i' = 1,2,\cdots, \lfloor K^{1/3} \rfloor\) 、 \(j'=1, 2, \cdots, \lfloor \sqrt{\frac{K}{i'}}\rfloor\) の範囲のみ調べれば十分です。
この決め方は \(O(K^{2/3})\) あります。
略証
\({\displaystyle\int_{1}^{K^{1/3}}}
\sqrt{\frac{K}{t}}\ dt = 2(K^{2/3} - K^{1/2}) \in O(K^{2/3})
\)
\(i', j'\) を決めると \(k'\) に関する二分探索で条件を満たす \(k'\) の個数が分かります。
添え字 \(i, j, k\) の大小関係をすべて試し、重複がないようにカウントすることで、 \(O(K^{2/3} \cdot \log N)\) で判定問題を解くことができます。
全体の計算量は \(O(K^{2/3} \cdot \log N \cdot \log M) \) です。
投稿日時:
最終更新: