LeetCode Weekly Contest 119 : 975. Odd Even Jump

なんかサイトが重く感じた。
https://leetcode.com/contest/weekly-contest-119/problems/odd-even-jump/

問題

N要素の数列A[0...(N-1)]が与えられる。
現在の位置iから、何度かジャンプを繰り返す。
その際以下のルールでジャンプする。

• 奇数回目のジャンプでは、i＜jかつA[i]≦A[j]を満たす最小のA[j]のうち最小のindex jにジャンプする。
• 偶数回目のジャンプでは、i＜jかつA[i]≧A[j]を満たす最大のA[j]のうち最小のindex jにジャンプする。
• いずれもジャンプ先のjが存在しない場合ジャンプできない。

各index iから初めてジャンプを繰り返すとき、index N-1に到達できる開始位置iは何通りか。

解法

現在位置で奇数回または偶数回目のジャンプを行う先の、移動先さえ求められれば、最終的にN-1に到達可能かは後ろから埋められる。
前者は自身よりあとの各数値の初出indexをmapで持っておけばlower_boundで判定可能。

class Solution {
public:
    int oddEvenJumps(vector<int>& A) {
		int N=A.size();
		vector<int> nex[2];
		vector<int> ok[2];
		map<int,int> S;
		int ret=0;
		int i;
		
		nex[0].resize(N);
		nex[1].resize(N);
		ok[0].resize(N);
		ok[1].resize(N);
		for(i=N-1;i>=0;i--) {
			if(i==N-1) {
				ok[0][i]=ok[1][i]=1;
				ret++;
			}
			else if(i<N-1) {
				
				auto it=S.lower_bound(A[i]);
				if(it==S.end()) {
					nex[0][i]=-1;
				}
				else {
					nex[0][i]=it->second;
					if(ok[1][nex[0][i]]) {
						ok[0][i]=1;
						ret++;
					}
				}
				
				it=S.lower_bound(A[i]+1);
				if(it==S.begin()) {
					nex[1][i]=-1;
				}
				else {
					it--;
					nex[1][i]=it->second;
					if(ok[0][nex[1][i]]) {
						ok[1][i]=1;
					}
				}
			}
			S[A[i]]=i;
		}
		return ret;
        
    }
};

まとめ

これSRMならDiv1 Easyクラスの問題な気がするなぁ。