Pythonで隣接しない要素ペアの最小合計を効率的に求める方法

問題概要

数値のリスト nums が与えられたとき、インデックスのペア (i, j) のうち、i < j かつ j − i > 1 を満たすもの、つまり互いに隣接していない要素同士のペアを考えます。その中で最も小さくなるペアの合計値を求めるのがこの問題です。

例えば、入力が nums = [3, 4, 2, 2, 4] の場合、出力は 5 になります。これは値 3 と 2 を選ぶと合計が 5 になるためです。なお、2 と 2 の組み合わせは選べません。この2つの要素は隣接しているため、j − i > 1 という制約に違反するからです。

解き方のアプローチ

この問題は、リストを一度だけ走査する線形時間 O(n) のアルゴリズムで効率的に解けます。ポイントは「現在の要素より2つ以上前までの範囲における最小値」を保持しておくことです。そうすることで、各位置 i において、nums[i] とペアにできる候補(インデックスが i − 2 以前の要素)の中の最小値と即座に組み合わせて答えを更新できます。

アルゴリズムの手順

• n: nums のサイズを取得します。
• min_seen: それまでに見た要素の最小値として、まず nums[0] で初期化します。
• ans: 答えを無限大(float("inf"))で初期化します。
• i を 2 から n − 1 まで繰り返します。
  • ans を、現在の ans と (min_seen + nums[i]) の小さい方で更新します。
  • min_seen を、現在の min_seen と nums[i − 1] の小さい方で更新します。
• 最後に ans を返します。

ここで重要なのは、min_seen の更新を ans の更新より後に行う点です。こうすることで、nums[i] と比較される候補は必ずインデックス差が 2 以上の要素だけになり、「隣接するペアは使えない」という制約が自然に守られます。

実装例(Python)

以下のコードで実際の動作を確認できます。

def solve(nums):
    n = len(nums)
    min_seen = nums[0]

    ans = float("inf")

    for i in range(2, n):
        ans = min(ans, min_seen + nums[i])

        min_seen = min(min_seen, nums[i - 1])
    return ans

nums = [3, 4, 2, 2, 4]
print(solve(nums))

入力

[3, 4, 2, 2, 4]

出力

5

まとめ

このアルゴリズムでは、リストを1回走査するだけで答えが求まるため、計算量は O(n)、追加のメモリ使用量は O(1) となります。全ペアを総当たりすると O(n²) かかるところを、累積最小値を活用することで大幅に高速化できるのがポイントです。「隣接しない要素を選ぶ」「間隔に制約があるペアの最適化」といった類題にも応用できるテクニックなので、ぜひ覚えておきましょう。