Pythonでリストの両端からペアを作り、合計を揃えるための最小操作回数を求めるプログラム

偶数の長さをもつ整数リスト nums が与えられます。実行できる操作は「nums 内の任意の要素を、1 以上 nums の最大値以下の値に更新する」というものです。すべての i について nums[i] + nums[n-1-i] が同じ値になるようにするには、最小で何回の操作が必要かを求めます。

たとえば、入力が nums = [8,6,2,5,9,2] の場合、出力は 2 になります。nums[2] の 2 を 5 に、nums[4] の 9 を 4 に変更するとリストは [8,6,5,5,4,2] となり、各 i に対する nums[i] + nums[n-1-i] は (8+2) = (6+4) = (5+5) = 10 ですべて一致します。

解法のアプローチ

この問題は、イベント（差分）をソートしながら走査する「スイープ」手法で効率的に解けます。目標となる合計値を T としたとき、各ペア (a, b) のコストは次のように分類できます。

• コスト 0： a + b がちょうど T と一致する場合（変更不要）
• コスト 1： 片方の要素だけを変更すれば T にできる場合。T が区間 [min(a+1, b+1), max(a+mx, b+mx)] に含まれるときに可能です（mx はリスト内の最大値）
• コスト 2： 上記以外の場合（両方の要素を変更する必要がある）

そこで、各ペアについて「コスト 1 で達成できる区間の開始」に +1、「その終了直後」に -1、さらに「ちょうど一致する点 a+b」に +1、「その直後」に -1 というイベントを登録します。これらをソートして累積していき、累積値の最大値 mx_same（＝コストを 0 または 1 に抑えられるペア数の最大値）を求めれば、答えは N − mx_same となります。

手順

• N := nums のサイズ、mx := nums の最大値とする
• events := 空のリスト、idx := 0 とする
• idx < N // 2 の間、次を繰り返す
  • a := nums[idx]、b := nums[N − idx − 1]
  • events の末尾に (min(a+1, b+1), 1) を追加
  • events の末尾に (a+b, 1) を追加
  • events の末尾に (a+b+1, −1) を追加
  • events の末尾に (max(a+mx, b+mx)+1, −1) を追加
  • idx := idx + 1
• events をソートする
• current := 0、mx_same := 0 とする
• events の各要素 (event, delta) について、current := current + delta とし、mx_same := max(current, mx_same) で更新する
• N − mx_same を返す

実装例

理解を深めるために、以下の Python 実装を見てみましょう。

def solve(nums):
    N = len(nums)
    mx = max(nums)
    events = []

    idx = 0
    while idx < N // 2:
        a = nums[idx]
        b = nums[N - idx - 1]

        events.append((min(a + 1, b + 1), 1))
        events.append((a + b, 1))
        events.append((a + b + 1, -1))
        events.append((max(a + mx, b + mx) + 1, -1))

        idx += 1

    events.sort()
    current = 0
    mx_same = 0

    for event, delta in events:
        current += delta
        mx_same = max(current, mx_same)

    return N - mx_same

nums = [8, 6, 2, 5, 9, 2]
print(solve(nums))

入力例

[8, 6, 2, 5, 9, 2]

出力例

2

計算量

各ペアにつき定数個（4 個）のイベントを登録するため、全体の時間計算量はソートを含めて O(N log N)、空間計算量は O(N) です。