Pythonで偶数番目と奇数番目のインデックス要素の合計を等しくするために削除できる要素の数を求めるプログラム

数値のリスト nums が与えられているとします。ここで関数 f(i) を考えます。この関数はインデックス i の要素を削除し、その結果のリストにおける偶数インデックスの値の合計と奇数インデックスの値の合計が等しいかどうかに応じて true または false を返します。求めたいのは、f が true を返すようなインデックスの個数です。

例えば、入力が nums = [6, 8, 5, 2, 3] の場合、出力は 2 になります。なぜなら、8 を削除すると配列は [6, 5, 2, 3] となり、偶数インデックスと奇数インデックスの要素の合計はどちらも 8 で等しくなるからです。もう一つの解は 2 を削除する場合で、このとき配列は [6, 8, 5, 3] となり、偶数・奇数インデックスの要素の合計はどちらも 11 で等しくなります。

解法のアプローチ

この問題を解くために、以下の手順に従います。

• n := nums のサイズ
• a := 2 × (n+1) の二次元リストを作成し、すべて 0 で初期化
• nums の各インデックス i と値 x に対して、以下を実行
  • a[0, i + 1] := a[0, i]
  • a[1, i + 1] := a[1, i]
  • a[i mod 2, i + 1] := a[i mod 2, i + 1] + x
• c := 0
• s := nums 内の全要素の合計
• i が 0 から n - 1 までの範囲で、以下を実行
  • e := a[0, i] - a[0, 0] + a[1, n] - a[1, i + 1]
  • e * 2 が s - nums[i] と等しい場合
    • c := c + 1
• c を返す

アルゴリズムのポイント

この解法の鍵となるのは「累積和」の活用です。二次元リスト a は、偶数インデックスと奇数インデックスそれぞれについて、先頭からの累積和を保持しています。ある要素を削除すると、それ以降の要素のインデックスの偶奇が入れ替わるため、削除後の偶数インデックスの合計は「削除位置より前の偶数インデックス部分」と「削除位置より後の奇数インデックス部分」の和になります。この性質により、各削除候補を O(1) で判定でき、全体の計算量は O(n) に抑えられます。

実装例

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

def solve(nums):
   n = len(nums)
   a = [[0] * (n + 1), [0] * (n + 1)]
   for i, x in enumerate(nums):
      a[0][i + 1] = a[0][i]
      a[1][i + 1] = a[1][i]
      a[i % 2][i + 1] += x

   c = 0
   s = sum(nums)
   for i in range(n):
      e = a[0][i] - a[0][0] + a[1][n] - a[1][i + 1]
      if e * 2 == s - nums[i]:
         c += 1
   return c

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

入力

[6, 8, 5, 2, 3]

出力

2