Pythonで配列を相補的な状態にするための最小操作回数を求めるプログラム

問題の概要

長さが偶数の配列 nums と整数 limit が与えられるとします。1回の操作では、nums 内の任意の要素を、1 以上 limit 以下の範囲の別の値に置き換えることができます。そして、すべてのインデックス i について nums[i] + nums[n-1-i] が常に同じ値になるとき、この配列は相補的（complementary）であると定義されます。この記事では、配列 nums を相補的な状態にするために必要な最小の操作回数を求める方法を解説します。

具体例

たとえば、入力が nums = [1,4,2,3]、limit = 4 の場合を考えてみましょう。このとき出力は 1 になります。1回の操作でインデックス 1 の要素（値 4）を 2 に書き換えれば、配列は [1,2,2,3] となり、次のようにすべてのペアの和が 4 に揃うためです。

• nums[0] + nums[3] = 1 + 3 = 4
• nums[1] + nums[2] = 2 + 2 = 4

解法のアプローチ：区間スキャンによる効率化

配列は前半と後半の要素がペアを組む構造になっています。n を配列の長さ、mid = n / 2 とすると、(nums[i], nums[n-1-i]) のような mid 組のペアが存在します。目標となる和 target（2 ～ 2×limit の範囲）を固定したとき、各ペアにかかるコストは次の3通りに分類できます。

• 0回： ペアの現在の和がちょうど target に等しい場合
• 1回： 片方の要素だけを書き換えて target にできる場合。具体的には min(x, y) + 1 ≤ target ≤ max(x, y) + limit を満たすとき
• 2回： 上記のいずれにも当てはまらない場合

そこで、target の値を 2 から 2 × limit まで順に走査しながら、「1回の操作で済むペアの個数（intervals）」を差分更新していきます。各区間の始点と終点をあらかじめ配列 start・end に記録しておけば、各 target における合計コストを O(1) で計算でき、全体の最小値を効率よく求められます。

アルゴリズムの手順

• n ← nums のサイズ
• mid ← n / 2 の商（小数点以下切り捨て）
• zero_moves ← 整数値を格納する空の辞書（マップ）
• start ← サイズ 2 × limit + 1 の配列を 0 で初期化
• end ← サイズ 2 × limit + 1 の配列を 0 で初期化
• res ← 無限大
• i を 0 から mid - 1 まで繰り返す：
  • x ← nums[i]、y ← nums[n - 1 - i]
  • zero_moves[x + y] を 1 増やす
  • start[min(x, y) + 1] を 1 増やす（1回で済む区間の始点）
  • end[max(x, y) + limit] を 1 増やす（同区間の終点）
• intervals ← 0
• target を 2 から limit × 2 まで繰り返す：
  • intervals ← intervals + start[target]
  • cost ← 2 × (mid - intervals) + intervals - zero_moves[target]
  • res ← res と cost の小さい方
  • intervals ← intervals - end[target]
• res を返す

コストの式 2 × (mid - intervals) + intervals - zero_moves[target] は次のように理解できます。まず、どの区間にも含まれない mid - intervals 組のペアは、それぞれ 2 回の操作が必要です。一方、区間に含まれる intervals 組のうち、すでに和が target と一致している zero_moves[target] 組は 0 回で済み、残りのペアは 1 回で済みます。これらを合計すると上記の式になります。

Pythonでの実装例

それでは、実際の実装を見てみましょう。

from collections import defaultdict

def solve(nums, limit):
    n = len(nums)
    mid = n // 2

    # 和が target と完全一致するペアの個数を記録
    zero_moves = defaultdict(int)

    # 「1回の操作で target に到達できる区間」の始点と終点
    start = [0] * (2 * limit + 1)
    end = [0] * (2 * limit + 1)
    res = float('inf')

    for i in range(mid):
        x = nums[i]
        y = nums[n - 1 - i]
        zero_moves[x + y] += 1
        start[min(x, y) + 1] += 1
        end[max(x, y) + limit] += 1

    intervals = 0
    for target in range(2, limit * 2 + 1):
        intervals += start[target]
        cost = 2 * (mid - intervals) + intervals - zero_moves[target]
        res = min(res, cost)
        intervals -= end[target]
    return res

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

実行結果

入力

[1,4,2,3], 4

出力

1

計算量

• 時間計算量： O(n + limit)。前半のループで各ペアを一度ずつ処理し、後半のループは target の候補数（最大 2×limit − 1 通り）を走査するだけです。
• 空間計算量： O(n + limit)。zero_moves 辞書と start・end 配列の保存にメモリを使用します。