Pythonで異なるパリティの値に到達するための最小ジャンプ数を求めるプログラム

問題の概要

数値のリスト nums が与えられていると仮定します。インデックス i からは、移動先がリストの範囲内に存在する限り、i + numbers[i] または i − numbers[i] の位置へジャンプすることができます。ここで求めたいのは、入力の順序を保ちながら、異なるパリティ（偶数・奇数の区別）を持つ別の値に到達するために必要な最小ジャンプ回数です。もし異なるパリティの数値にどうしても到達できない場合は、−1 を返します。

たとえば、入力が numbers = [7, 3, 4, 5, 6, 9, 6, 7] の場合、出力は [-1, 1, 2, -1, -1, -1, 1, -1] になります。

解き方のアプローチ：幅優先探索（BFS）

この種の「最短ステップ数」を求める問題は、幅優先探索（BFS）が最適です。BFSは近い位置から順に層状に探索を進めるため、最初に目的の状態（この場合はパリティが異なる値）に到達した時点のジャンプ回数が、必ず最小値になると保証されるからです。

具体的には、以下の手順で解きます。

1. bfs() 関数を定義する（開始位置 i を引数として受け取る）。

   • q := ペア (i, 0) を格納した新しい両端キュー（deque）を作成する。

   • seen := 訪問済みインデックスを管理するための新しいセットを作成する。

   • q が空でない限り、以下を繰り返す。

     • (j, d) := q の左端から要素を取り出して削除する（j は現在位置、d はそこまでのジャンプ回数）。

     • j を seen に追加する。

     • (nums[i] + nums[j]) mod 2 が 0 以外（＝両者のパリティが異なる）であれば、d を返す。

     • k が [j + nums[j], j − nums[j]] の各値であるとき、0 ≤ k < len(nums) を満たし、かつ k が seen に含まれていなければ、q の右端に (k, d + 1) を挿入する。

   • キューが空になった場合は、到達不可能を示す十分に大きな値 10^10 を返す。

2. メイン処理で以下を実行する。

   • ans := 結果を格納する新しいリストを作成する。

   • i を 0 から len(nums) − 1 までループし、bfs(i) の戻り値 x が 10^10 未満であれば ans に x を追加し、そうでなければ −1 を追加する。

   • ans を返す。

実装例

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

from collections import deque
class Solution:
    def solve(self, nums):
        def bfs(i):
            q = deque([(i, 0)])
            seen = set()
            while q:
                j, d = q.popleft()
                seen.add(j)
                if (nums[i] + nums[j]) % 2:
                    return d
                for k in [j + nums[j], j - nums[j]]:
                    if 0 <= k < len(nums) and k not in seen:
                        q.append((k, d + 1))
            return 10 ** 10
        ans = []
        for i in range(len(nums)):
            x = bfs(i)
            ans.append(x if x < 10 ** 10 else -1)
        return ans

ob = Solution()
print(ob.solve([7, 3, 4, 5, 6, 9, 6, 7]))

入力

numbers = [7, 3, 4, 5, 6, 9, 6, 7]

出力

[-1, 1, 2, -1, -1, -1, 1, -1]

出力の読み方

結果の意味を簡単に確認してみましょう。たとえば、インデックス 1（値は 3、奇数）からは、1 回のジャンプでインデックス 4（値は 6、偶数）に移動できるため、答えは 1 になります。一方、インデックス 0（値は 7、奇数）からはジャンプを繰り返しても偶数の値には一切たどり着けないため、−1 が返されます。

計算量について

各開始位置ごとに独立して BFS を実行しており、各探索では同じインデックスを 2 度以上訪問しないため、全体の時間計算量は O(n²) 程度に収まります。リストのサイズがそれほど大きくない場合には、十分実用的なアプローチです。