LeetCode Weekly Contest 424 : 3357. Minimize the Maximum Adjacent Element Difference

これは難易度8でもいいかも。
https://leetcode.com/problems/minimize-the-maximum-adjacent-element-difference/description/

問題

整数列Aが与えられる。
Aの一部の要素は未定である。

整数値を2つx,y定め、Aの未定の要素にxかyを代入できるとする。
この時、Aの隣接要素の差の絶対値の最大値を最小化せよ。

解法

解vを二分探索する。

Aのうち、隣接要素同士を見比べて片方が未定の場合、未定でない方を集めた数列をBとする。
x,yのうち小さい方をxが担当するとき、xをできるだけ大きく、yをできるだけ小さくすることを考える。
とするとx=min(B)+v、y=max(B)-vとなる。

Bのうち未定な要素を消したとき、間をx,yで埋めれば隣接要素間の差がv以下になるかを判定すればよい。

class Solution {
public:
	int can(ll v,vector<int> nums) {
		int i;
		int N=nums.size();
		ll x=1LL<<31;
		ll y=-1LL<<31;
		FOR(i,N-1) {
			if(nums[i]==-1&&nums[i+1]==-1) continue;
			else if(nums[i]==-1) {
				x=min(x,nums[i+1]+v);
				y=max(y,nums[i+1]-v);
			}
			else if(nums[i+1]==-1) {
				x=min(x,nums[i]+v);
				y=max(y,nums[i]-v);
			}
			else {
				if(abs(nums[i+1]-nums[i])>v) return 0;
			}
		}
		
		ll pre=-1LL<<30;
		int n1=0;
		//cout<<v<<" "<<x<<" "<<y<<endl;
		FOR(i,N) {
			//cout<<"#"<<i<<" "<<pre<<" "<<nums[i]<<" "<<n1<<endl;
			if(nums[i]!=-1) {
				int ok=0;
				if(pre<0) {
					ok=1;
				}
				else if(pre>0) {
					if(n1==0) {
						ok=1;
					}
					if(abs(pre-x)<=v&&abs(nums[i]-x)<=v) ok=1;
					if(abs(pre-y)<=v&&abs(nums[i]-y)<=v) ok=1;
					if(n1>=2) {
						if(x+v>=y) ok=1;
					}
					if(ok==0) return 0;
				}
				n1=0;
				pre=nums[i];
			}
			else {
				n1++;
			}
		}
		return 1;
		
	}
    int minDifference(vector<int>& nums) {
		int N=nums.size();
		
		int ret=(1<<30)-1;
		int i;
		for(i=29;i>=0;i--) if(can(ret-(1<<i),nums)) ret-=1<<i;
		return ret;
        
    }
};

まとめ

コーナーケースとか地味に面倒な問題。