LeetCode Weekly Contest 362 : 2935. Maximum Strong Pair XOR II

また唐突な難易度8。
https://leetcode.com/contest/weekly-contest-371/problems/maximum-strong-pair-xor-ii/

問題

整数列Aが与えられる。
A中の2要素x,yの組に対し、|x-y|≦min(x,y)であるもののうちx xor yの最大値を求めよ。

解法

対称性よりy≦xを仮定すると、y≦x≦2*yである。
よって、Aをソートしておけば、yを総当たりしながら、取りえるxの含まれる区間を尺取り法で絞ることができる。
あとは、区間内でyとxorを取ると最大値になるものを2進数表記で上の桁から絞り込んでいけばよい。

vector<int> V;

class Solution {
public:
	int hoge(int L,int R,int v,int cv,int d) {
		if(d==-1) return V[L];
		
		int M=lower_bound(V.begin()+L,V.begin()+R,cv+(1<<d))-V.begin();
		if(L==M) return hoge(M,R,v,cv+(1<<d),d-1);
		if(M==R) return hoge(L,M,v,cv,d-1);
		
		if(v&(1<<d)) return hoge(L,M,v,cv,d-1);
		else return hoge(M,R,v,cv+(1<<d),d-1);
		
		
		
	}
    int maximumStrongPairXor(vector<int>& nums) {
		int N=nums.size();
		sort(ALL(nums));
		V=nums;
		int ma=0;
		for(int L=0,R=0;L<N;L++) {
			while(R<N&&V[R]<=2*V[L]) R++;
			ma=max(ma,V[L]^hoge(L,R,V[L],0,19));
		}
        return ma;
    }
};

まとめ

難易度7でもいい気はするけどね。