C++で解く「奇数・偶数ジャンプ」問題：配列の末尾に到達できる開始位置の数え方

問題の概要

配列 A が与えられたとします。任意の開始インデックスから出発し、一連のジャンプを行うことを考えます。このとき、系列の中で1回目・3回目・5回目…にあたるジャンプを奇数番目のジャンプ、2回目・4回目・6回目…にあたるジャンプを偶数番目のジャンプと呼びます。

インデックス i から前方のインデックス j（i < j）へは、以下のルールでジャンプできます。

• 奇数番目のジャンプの場合： A[i] <= A[j] を満たすインデックス j のうち、A[j] が最小となるものへ移動します。該当する j が複数ある場合は、最も小さいインデックス j を選びます。
• 偶数番目のジャンプの場合： A[i] >= A[j] を満たすインデックス j のうち、A[j] が最大となるものへ移動します。こちらも該当する j が複数ある場合は、最も小さいインデックス j を選びます。
• 場合によっては、あるインデックス i から有効なジャンプ先が存在しないこともあります。

このとき、その開始インデックスから出発して何回かのジャンプを経由して配列の末尾に到達できるなら、その開始インデックスを「良い（good）」開始インデックスと呼びます。

私たちの課題は、この良い開始インデックスの総数を求めることです。

例えば入力が [10,13,12,14,15] の場合、出力は 2 になります。これは、インデックス 3 と 4 の2箇所から配列の末尾へ到達できるためです。

解法のアプローチ

この問題を解くために、次の手順に従います。

• 答えを格納する変数 ret := 1 で初期化します（末尾の要素自身が常に良い開始位置であるため）。
• n := 配列 A のサイズ とします。
• サイズ n の配列 nextGreaterEqual を定義し、すべて -1 で埋めます。
• 同様に、サイズ n の配列 nextSmallerEqual を定義し、すべて -1 で埋めます。
• マップ st を1つ用意します。
• i を n - 1 から 0 まで減らしながらループ処理を行います。
  • A[i] 以上の値を持つ最小のキー（lower_bound）をマップから探します。
  • nextGreaterEqual[i] := 見つかった要素がマップの末尾でなければその値、そうでなければ -1。
  • もし見つかったキーが A[i] と等しければ、イテレータを1つ進めます。
  • nextSmallerEqual[i] := イテレータがマップの先頭でなければ直前の要素の値、そうでなければ -1。
  • st[A[i]] := i を登録します。
• サイズ n × 2 の2次元配列 v を定義し、すべて false で初期化します。
• v[n - 1][0] = v[n - 1][1] = true と設定します（末尾からは常に到達済み）。
• i を n - 2 から 0 まで減らしながらループ処理を行います。
  • nextGreaterEqual[i] が -1 でない場合、v[i][1] := v[nextGreaterEqual[i]][0] と更新します。
  • nextSmallerEqual[i] が -1 でない場合、v[i][0] := v[nextSmallerEqual[i]][1] と更新します。
  • v[i][1] が true であれば ret を1増やします。
• 最後に ret を返します。

ここでのポイントは、各位置から「奇数ジャンプ後に到達可能な次の位置」と「偶数ジャンプ後に到達可能な次の位置」を事前に計算しておき、動的計画法（DP）で末尾への到達可能性を逆順に伝播させていく点です。これにより O(n log n) の時間計算量で効率的に答えを求められます。

C++による実装例

それでは、理解を深めるために実際のコードを見てみましょう。

#include <bits/stdc++.h>
using namespace std;
class Solution {
    public:
    int oddEvenJumps(vector<int>& A){
        int ret = 1;
        int n = A.size();
        vector<int> nextGreaterEqual(n, -1);
        vector<int> nextSmallerEqual(n, -1);
        map<int, int> st;
        for (int i = n - 1; i >= 0; i--) {
            map<int, int>::iterator it = st.lower_bound(A[i]);
            nextGreaterEqual[i] = (it != st.end()) ? it->second : -1;
            if (it != st.end() && it->first == A[i])
            it++;
            nextSmallerEqual[i] = it != st.begin() ? prev(it)->second
            : -1;
            st[A[i]] = i;
        }
        vector<vector<bool> > v(n, vector<bool>(2, false));
        v[n - 1][0] = v[n - 1][1] = true;
        for (int i = n - 2; i >= 0; i--) {
            if (nextGreaterEqual[i] != -1) {
                v[i][1] = v[nextGreaterEqual[i]][0];
            }
            if (nextSmallerEqual[i] != -1) {
                v[i][0] = v[nextSmallerEqual[i]][1];
            }
            if (v[i][1])
            ret++;
        }
        return ret;
    }
};
main(){
    Solution ob;
    vector<int> v = {10,13,12,14,15};
    cout << (ob.oddEvenJumps(v));
}

入力

{10,13,12,14,15}

出力

2

まとめ

この問題では、std::map の lower_bound を活用することで、「次にジャンプ可能な位置」を対数時間で高速に探索できるのが鍵となります。末尾側から DP テーブルを埋めていくことで、各開始インデックスが良い開始位置かどうかを一度の走査で判定でき、全体として O(n log n) の計算量で解ける効率的なアルゴリズムになっています。