Pythonで配列の偏差を最小化するプログラムの実装方法

問題の概要

配列 nums が与えられます。配列内の任意の要素に対して、次の2種類の操作を何度でも実行できます。

• 偶数の要素は 2 で割る
• 奇数の要素は 2 倍する

ここで、配列の「偏差」とは、配列内の任意の2つの要素間の差のうち最大のものを指します。求めたいのは、操作を何度か実行した後に配列が取りうる偏差の最小値です。

具体例

入力が nums = [6,3,7,22,5] の場合、答えは 5 になります。実際の操作の流れは次のとおりです。

1. 1回目の操作：3 を 2 倍して [6,6,7,22,5]
2. 2回目の操作：5 を 2 倍して [6,6,7,22,10]
3. 3回目の操作：22 を 2 で割って [6,6,7,11,10]

この状態での偏差は 11 − 6 = 5 となり、これ以上小さくすることはできません。

解法のアプローチ

この問題は、優先度付きキュー（ヒープ）を活用することで効率的に解けます。解決の手順は以下のとおりです。

1. リスト nums をソートする
2. max_v を nums の最大値、min_v を最小値として初期化する
3. nums を最小ヒープ化する
4. 初期解として res = max_v - min_v を設定する
5. ヒープの先頭（最小値）が奇数である間、次を繰り返す
   • 最小値を取り出して 2 倍し、ヒープに戻す
   • min_v を現在のヒープの先頭で更新する
   • max_v を v と max_v の大きい方で更新する
   • res を res と (max_v - min_v) の小さい方で更新する
6. すべての要素の符号を反転して再度ヒープ化し、最大ヒープとして扱う
7. ヒープの先頭（最大値）が偶数である間、次を繰り返す
   • 最大値を取り出して 2 で割り、符号を反転してヒープに戻す
   • max_v を現在のヒープの先頭（符号反転後の値）で更新する
   • min_v を min_v と v の小さい方で更新する
   • res を res と (max_v - min_v) の小さい方で更新する
8. res を返す

アルゴリズムのポイント

このアプローチが機能するのは、各要素が到達できる値が限定されているためです。奇数を 2 倍すると必ず偶数になり、偶数を 2 で割り続けると最終的に奇数になります。つまり、偏差を縮めるには「最小値が奇数なら 2 倍して押し上げる」か「最大値が偶数なら 2 で割って押し下げる」しかありません。Python の heapq モジュールは最小ヒープのみを提供しているため、2番目のフェーズでは要素の符号を反転することで最大ヒープを実現しています。

Pythonによる実装例

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

import heapq
def solve(nums):
   nums.sort()
   max_v,min_v = nums[-1],nums[0]
   heapq.heapify(nums)
   res = max_v-min_v
   while nums[0]%2==1:
      v = heapq.heappop(nums)
      v = 2 * v
      heapq.heappush(nums, v)
      min_v = nums[0]
      max_v = max(v, max_v)
      res = min(res, max_v - min_v)

   nums = [-n for n in nums]
   heapq.heapify(nums)
   while nums[0]%2==0:
      v = -heapq.heappop(nums)
      v = v // 2
      heapq.heappush(nums, -v)
      max_v = -nums[0]
      min_v = min(min_v,v)
      res = min(res, max_v - min_v)

   return res

nums = [6,3,7,22,5]
print(solve(nums))

入力と出力

入力

[6,3,7,22,5]

出力

5

計算量について

ヒープへの挿入・削除にはそれぞれ O(log n) のコストがかかります。また、各要素が取りうる値の候補数は高々 O(log M) 個（M は要素の最大値）に抑えられるため、全体の計算量は O(n log n log M) となり、大きな入力に対しても十分高速に動作します。