kmjp's blog

競技プログラミング参加記です

LeetCode Weekly Contest 438 : 3464. Maximize the Distance Between Points on a Square

これはそこまで難しくないな。
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を大きくしてダブリング必須にしてもよいと思ったけどな。