Pythonでk回のジャンプで最後の島に到達する：ジャンプ最大距離の最小値を二分探索で求める

問題概要

数列 A が与えられ、A の i 番目の要素は i 番目の島の位置を表しているとします。さらに整数 k（1 ≤ k < N）も与えられます。ここで、ある人が 0 番目の島からスタートし、ちょうど k 回のジャンプで最後の島に到達しなければなりません。その際、移動中に行う「1 回のジャンプの長さ」の最大値が最小になるようにしたとき、その値を求めるのがこの問題です。

なお、すべての島の位置は昇順に並んでいるものとします。

入力例と出力例

たとえば、入力が A = [7, 20, 41, 48]、k = 2 の場合、出力は 28 になります。理由を見てみましょう。

• 経路 1：7 → 20 → 48
  隣り合う島同士の距離は 13 と 28 となり、最大値は 28
• 経路 2：7 → 41 → 48
  隣り合う島同士の距離は 34 と 7 となり、最大値は 34

両者を比較すると小さい方は 28 なので、答えは 28 となります。

解法のアプローチ：二分探索

この問題は、「ジャンプの最大長を d 以下に抑えたとき、k 回以内のジャンプでゴールに到達できるか？」という判定問題に帰着できます。d が大きくなるほど到達しやすくなる（単調性がある）ため、二分探索によって d の最小値を効率的に求められます。

アルゴリズムの手順

1. 判定用の関数 isPossible(arr, dist, k) を定義します。
2. 配列のサイズを n とし、必要なジャンプ回数 req、現在注目している位置 current、前回の出発地点 previous を初期化します。
3. 各ステップでは、dist 以内で到達できる限り current を先へ進め、そこまでの移動を 1 回のジャンプとしてカウントします。
4. 最後の島に到達できなかった場合、または必要なジャンプ回数が k を超える場合は False を返します。
5. メイン処理では、left = 0、right = 配列の最後の要素として二分探索を実行し、条件を満たす最小の dist を求めます。

Pythonでの実装例

def isPossible(arr,dist, k) :
    n = len(arr)
    req = 0
    current = 0
    previous = 0
    for i in range(0, n):
        while (current != n and (arr[current] - arr[previous]) <= dist):
            current += 1
        req += 1
        if (current == n):
            break
        previous = current - 1
    if (current != n):
        return False
    if (req <= k):
        return True
    return False

def minimum_distance(arr, k):
    n = len(arr)
    left = 0
    right = arr[-1]
    ans = 0
    while (left <= right):
        mid = (left + right) // 2;
        if (isPossible(arr, mid, k)):
            ans = mid
            right = mid - 1
        else:
            left = mid + 1
    return ans

arr = [7, 20, 41, 48]
k = 2
print(minimum_distance(arr, k))

入力

[7, 20, 41, 48] , 2

出力

28

計算量について

判定関数 isPossible は配列を一度走査するだけなので O(N)、二分探索は最大でも O(log D) 回繰り返されます（D は座標の最大値）。したがって全体の計算量は O(N log D) となり、N や座標の範囲が大きいケースでも効率的に動作します。