E - 道路の建設案 (Road Construction) Editorial by Nachia


計算量 \(O(N\log\log w+N\log N+K\log K)\) ( \(w\)\(X _ i\) , \(Y _ i\) の絶対値の最大値の制約 \(=10^9\) ) の方法です。永続セグメント木を用いる公式解説の方法と比べるとオーダーは劣りますが、実際には多くのケースで高速です。

\((x,y)\)\((x+y+2w,x-y+2w)\) に移動する変換 (\(45\) 度回転) をします。扱う値は非負整数になり、 \(2\)\((x_1,y_1),(x_2,y_2)\) 間の距離は \(\max\lbrace |x_1-x_2|,|y_1,y_2| \rbrace\) となります。

非負整数 \(k\) について、点をブロック \(B_{(k,a,b)} = \lbrace (x,y) \vert (\lfloor x/2^k \rfloor, \lfloor y/2^k \rfloor )=(a,b) \rbrace \) で分割し、ブロック内で \(2\) 点の組を作ります。このとき、作る組の個数が \(K\) 以上になる最小の \(k\) を求めます。分割は Quadtree (Wikipedia) 上の位置をビット列で表すと都合がよいです。このビット列は点 \((x,y)\) について \(x\)\(y\) のビット列を交互にしたものとします。これは、ワード長を利用したビット演算を用いて各点で計算量 \(O( \log \log w)\) で求まります。すると、ある \(k\) に対して組の個数は尺取り法により計算量 \(O(N)\) で計算でき、 \(k\) の二分探索を含めると計算量 \(O(N\log N + N \log \log w)\) です。

出力すべき距離はすべて \(2^k-1\) 以下であることが分かります。よって、考慮すべき点対は同一のブロックまたは(ブロックを正方形として見たときの)辺または頂点で接する \(2\) ブロックに含まれます。よって、この条件を満たす点対をすべて探索します。

ブロックの検索は先に求めたビット列の検索で毎回計算量 \(O( \log N)\) です。探索する点対の個数は、 ABC234Ex - Enumerate Pairs と同様の議論で \(O(N+K)\) とわかります(が、恐らくは恣意的なケースでは定数倍が無視できないでしょう)。

求めた点対を距離で昇順ソートすると、必要なものが求まります。

実装によっては \(64\) ビットの整数型では足りないので、注意が必要です。

解答例

posted:
last update: