これはそこまで難しくないな。
https://leetcode.com/problems/maximize-the-distance-between-points-on-a-square/description/
問題
(0,0)-(side,0)-(side,side)-(0,side)を結んだ正方形がある。
この辺上にいくつかの点が与えられる。
ここからK点選んだ時、互いのマンハッタン距離の最小値を最大化したい。その値を求めよ。
解法
解dを二分探索する。
各頂点を、正方形をぐるりと回る向きで並べたとき、K個選んで隣接する点同士のマンハッタン距離がd以上か確認すればよい。
あらかじめ各点からd以上の距離を持つ最寄りの点の番号がわかるなら、各点からそれをK回たどったとき、1周以下でK点取れるならd以上のマンハッタン距離を確保できることがわかる。
幸いKが小さいので、ダブリングは不要。
int nex[303030]; class Solution { public: int maxDistance(int side, vector<vector<int>>& points, int k) { vector<ll> cand; FORR(e,points) { if(e[1]==0) cand.push_back(e[0]); else if(e[0]==side) cand.push_back(side+e[1]); else if(e[1]==side) cand.push_back(2LL*side+side-e[0]); else cand.push_back(4LL*side-e[1]); cand.push_back(4LL*side+cand.back()); } sort(ALL(cand)); ll ret=0; int i,j; int N=cand.size(); for(i=30;i>=0;i--) { ll tmp=ret+(1<<i); if(tmp*k>4LL*side) continue; int x,y; for(x=y=0;x<N;x++) { while(y<N&&cand[y]-cand[x]<tmp) y++; nex[x]=y; } FOR(x,N/2) { int cur=x; FOR(j,k) { cur=nex[cur]; if(cur==N) break; } if(cur<=x+N/2) break; } if(x<N/2) ret=tmp; } return ret; } };
まとめ
難易度8なら、Kを大きくしてダブリング必須にしてもよいと思ったけどな。