循環リストに一方向のみのサイクルが存在するか判定するPythonプログラム

問題概要

循環リスト nums を考えてみましょう。このリストでは、最初の要素と最後の要素が互いに隣接しています。任意のインデックス i から出発し、nums[i] が正の値であれば nums[i] ステップだけ前進し、負の値であれば後退します。このとき、「長さが1より大きく、かつ経路が前方への移動のみ、または後方への移動のみで構成される」サイクル（ループ）が存在するかどうかを判定する必要があります。

例えば、入力が nums = [-1, 2, -1, 1, 2] の場合、前方への経路 [1 → 3 → 4 → 1] が存在するため、出力は True になります。

解法のアプローチ

この問題は、各開始地点から実際に移動をシミュレートしながら、訪問履歴を記録することで解けます。具体的な手順は以下の通りです。

• n を nums のサイズとします
• n が 0 の場合は False を返します
• seen をサイズ n の配列として作成し、すべて 0 で初期化します
• nums の各要素 x を「x mod n」に変換して正規化します
• iter を 0 で初期化します
• i を 0 から n-1 まで順に処理します：
  • nums[i] が 0 の場合は次の反復へスキップします
  • iter を 1 増やします（新しい探索の識別番号）
  • pos と neg を True に設定します
  • curr を i に設定します
  • 以下を繰り返します：
    • nums[curr] が非ゼロで、seen[curr] が iter と等しい場合は True を返します（同一探索内での再訪問＝サイクル発見）
    • seen[curr] が非ゼロの場合はループを抜けます（過去の探索で訪問済み）
    • nums[curr] > 0 の場合は neg を False に、それ以外の場合は pos を False にします
    • neg と pos の両方が False になったらループを抜けます（方向が混在しているため条件不成立）
    • seen[curr] を iter に設定します
    • curr を (curr + nums[curr] + n) mod n に更新します
    • nums[curr] が 0 の場合はループを抜けます
• 最後に False を返します

実装例

以下のPythonコードで理解を深めましょう。

def solve(nums):
    n = len(nums)
    if n == 0:
        return False
    seen = [0]*n
    nums = [x % n for x in nums]
    iter = 0
    for i in range(n):
        if nums[i] == 0:
            continue
        iter += 1
        pos = True
        neg = True
        curr = i
        while True:
            if nums[curr] and seen[curr] == iter:
                return True
            if seen[curr]:
                break
            if nums[curr] > 0:
                neg = False
            else:
                pos = False
            if not neg and not pos:
                break
            seen[curr] = iter
            curr = (curr + nums[curr] + n) % n
            if nums[curr] == 0:
                break
    return False

nums = [-1, 2, -1, 1, 2]
print(solve(nums))

入力

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

出力

True

アルゴリズムのポイント

このアルゴリズムの鍵となるのは、訪問管理に使う seen 配列と、各探索の試行に割り当てる一意の番号 iter です。同じ試行内で既に訪問したインデックスに戻ってきた場合、そこにサイクルが存在することを意味します。一方、過去の試行で訪問済みのインデックスに到達した場合は、新たなサイクルにはならないため探索を打ち切ります。

また、pos と neg の2つのフラグにより、経路が一方向のみであることを保証しています。移動中に前進と後退が混在すると両方のフラグが False になるため、その時点で条件を満たさないと判断して効率的に探索を終了できます。計算量は O(n²) となり、各要素は高々一度ずつ訪問されるため無駄がありません。