Pythonで解く「配列分割 I」：最小値の和を最大化するアルゴリズムと実装例

問題の概要

2n 個の整数からなる配列が与えられたとき、これらの整数を (a1, b1), (a2, b2), ..., (an, bn) のように n 組のペアに分组することを考えます。その際、各ペアの小さい方の値、つまり min(ai, bi) をすべて合計した値が最大になるようにペアを作る必要があります。

例えば、入力が [1, 4, 3, 2] の場合、出力は 4 となります。このとき n = 2 であり、最適なペアの組み合わせは次のようになります。

min(1, 2) + min(3, 4) = 1 + 3 = 4

解法のアプローチ

この問題は貪欲法（グリーディ法）で効率よく解くことができます。ポイントは「配列を昇順にソートすると、隣り合う要素同士をペアにするのが最適」という性質です。大きい要素同士をペアにしてしまうと、片方が捨てられてしまうため損になります。以下の手順で解きます。

• n を配列のサイズとする
• 配列を昇順にソートする
• answer を 0 で初期化する
• i を 0 から n まで 2 ずつ増やしながらループする
  • answer := answer + array[i]
• answer を返す

ソート後、インデックス 0, 2, 4, ... の位置にある要素（各ペアのうち小さい方）を足し合わせるだけで答えが求まります。計算量はソート部分が支配的で、O(n log n) となります。

Pythonでの実装例

以下のコードで実際の実装を確認してみましょう。

class Solution(object):
   def arrayPairSum(self, a):
      """
      :type nums: List[int]
      :rtype: int
      """
      n = len(a)
      a.sort()
      ans = 0
      for i in range(0,n,2):
         ans += a[i]
      return ans

ob1 = Solution()
print(ob1.arrayPairSum([1,4,3,2]))

入力

[1,4,3,2]

出力

4

まとめ

この問題の鍵となるのは、「ソートすれば隣接する2つの要素をペアにするのが常に最適」という直感です。もし隣接しない要素をペアにすると、間にある大きな値が min() の計算で切り捨てられてしまい、合計が小さくなります。したがって、ソート後に偶数番目の要素を合計するシンプルなアルゴリズムで、最大の合計値を求めることができます。