kmjp's blog

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

LeetCode Weekly Contest 142 : 1095. Find in Mountain Array

こっちはいいんだけどね…。
https://leetcode.com/contest/weekly-contest-142/problems/find-in-mountain-array/

問題

ある数列があり、その数列は山を成している。
すなわち、あるところまで真に単調増加で、その後真に単調減少となる。

この数列の具体的な中身は不明だが、最大で100個まで値を取得できるものとする。
値がTであるindexが存在するならそれを求めよ。

解法

まず最大値を特定しよう。
これは区間の三分探索で絞り込める。
区間の両端と、間2か所の計4か所の値を求めれば、そのうちの最大値の位置によって区間を2/3に絞れる。

最大値が特定できれば、単調増加の区間と単調減少の区間それぞれで二分探索するだけ。

int A[101010];


class Solution {
public:
	int get(int v,MountainArray &M) {
		if(A[v]==-1) A[v]=M.get(v);
		return A[v];
	}
    int findInMountainArray(int target, MountainArray &M) {
        MINUS(A);
        int N=M.length();
        int L=0,R=N-1;
        while(R-L>=6) {
			int m1=(2*L+R)/3;
			int m2=(L+2*R)/3;
			int V[4]={
				get(L,M),
				get(m1,M),
				get(m2,M),
				get(R,M),
			};
			
			if(V[0]==V[1]) R=m1;
			else if(V[0]==V[2]) R=m2;
			else if(V[1]==V[2]) L=m1,R=m2;
			else if(V[1]==V[3]) L=m1;
			else if(V[2]==V[3]) L=m2;
			else {
				int x=max_element(V,V+4)-V;
				if(x==0) R=m1;
				if(x==1) R=m2;
				if(x==2) L=m1;
				if(x==3) L=m2;
			}
		}
		int i;
		int id=L;
		for(i=L;i<=R;i++) {
			get(i,M);
			if(A[i]>A[id]) id=i;
		}
		
		if(A[0]<=target&&target<=A[id]) {
			int i;
			int cur=-1;
			for(i=20;i>=0;i--) if(cur+(1<<i)<=id && get(cur+(1<<i),M)<=target) cur+=1<<i;
			
			if(cur>=0 && get(cur,M)==target) return cur;
		}
		
		if(target<=A[id]&&target>=get(N-1,M)) {
			int i;
			int cur=id;
			for(i=20;i>=0;i--) if(cur+(1<<i)<N && get(cur+(1<<i),M)>=target) cur+=1<<i;
			
			if(get(cur,M)==target) return cur;
		}
		return -1;
        
    }
};

まとめ

interactive面倒だなと思って後回しにしたらあとがもっと面倒だった。