Pythonで「おいしい食事」の組み合わせを数えるアルゴリズム

問題の概要

「良い食事（Good Meal）」とは、ちょうど2つの異なる食品で構成され、そのおいしさの合計が2のべき乗（1, 2, 4, 8, 16, …）と一致する組み合わせを指します。食品リストの中から任意の2つを選んで「良い食事」を作ることができます。

ここでは、整数型の配列 arr が与えられ、arr[i] は i 番目の食品のおいしさを表すものとします。このリストから作成できる「良い食事」の組み合わせの総数を返す関数をPythonで実装してみましょう。

入力例1

arr[ ] = {1, 3, 5, 7, 9}

出力：

4

説明：「良い食事」となるのは (1,3)、(1,7)、(3,5)、(7,9) の4通りです。それぞれの合計は 4、8、8、16 であり、すべて2のべき乗になっています。

入力例2

arr[ ] = {1, 1, 1, 3, 3, 3, 7}

出力：

15

説明：(1,1) の組み合わせが3通り、(1,3) が9通り、(1,7) が3通りあり、合計15通りの「良い食事」が作れます。

解法のアプローチ

すべてのペアを総当たりで調べると計算量が O(n²) となり、要素数が多い場合に非効率です。そこでハッシュマップ（辞書）を使って、これまで登場した要素の出現回数を記録しながら処理することで、効率的に答えを求められます。

• 正の整数の配列を入力として受け取ります。

• countPairs 関数が、配列の全要素を整数のリストとして処理します。

• 入力配列の要素を昇順にソートします。

• 各要素 d について、d との合計が2のべき乗になる相手（n − d）がこれまでに何個現れたかを辞書から参照し、答えに加算します。

• 競技プログラミングで一般的なように、結果が大きくなりすぎないよう 10⁹ + 7 で剰余を取ります。

Pythonでの実装例

from collections import defaultdict
from typing import List

class Solution:
    def countPairs(self, arr: List[int]) -> int:
        """
        条件: elem1 + elem2 == 1 << i（2のべき乗）
        探す相手: elem1 = (1 << i) - elem2
        """
        result = 0
        seen = defaultdict(int)   # これまで見た値の出現回数
        arr.sort()
        for d in arr:
            n = 1
            while n <= d + d:     # d とペアになり得る最大の合計まで試す
                result = (result + seen[n - d]) % (10 ** 9 + 7)
                n = n << 1        # n を次の2のべき乗へ
            seen[d] += 1          # 自分自身を「既出」として登録
        return result

sol1 = Solution()
print(sol1.countPairs([1, 1, 1, 3, 3, 3, 7]))

実行結果

15

アルゴリズムのポイント

この手法の優れている点は以下の通りです。

• 計算量： 各要素に対してチェックすべき2のべき乗の候補は高々30個程度なので、全体の計算量はほぼ O(n log M) に抑えられます。総当たりの O(n²) よりも大幅に高速です。

• ソートの役割： 配列を昇順にソートしておくことで、「現在の要素 d とペアになり得る合計の上限は d + d」と保証でき、無駄なべき乗の探索を省けます。

• 重複の扱い： 同じ値が複数回現れても、辞書に出現回数を記録しているため、(1,1) のような同じ値同士のペアも正しく数えられます。