Pythonで解く！おいしさの合計が2のべき乗になる2品の組み合わせ（良い食事）を数える方法

問題概要

配列 deli が与えられ、deli[i] は i 番目の食品のおいしさを表します。このリストから作れる「良い食事」の総数を求めるのが目的です。ここで「良い食事」とは、ちょうど2つの異なる食品を選び、そのおいしさの合計が2のべき乗になる食事のことです。答えが非常に大きくなる可能性があるため、結果は 10^9 + 7 で割った余りを返します。

例えば、入力が deli = [1, 7, 3, 6, 5] の場合、出力は 3 になります。これは、(1, 3)、(1, 7)、(3, 5) の3組のペアについて、おいしさの合計がそれぞれ 4、8、8 となり、いずれも2のべき乗に一致するためです。

解法のアプローチ

この問題は、各値の出現回数を記録したマップ（カウンタ）を作成し、「2のべき乗との差分」がリスト内に存在するかを順番に調べることで効率的に解けます。手順は以下の通りです。

• m := 10^9 + 7（剰余を取るための定数）
• count := 各おいしさの値の出現頻度を格納するマップ
• ans := 0（答えを格納する変数）
• count 内の各要素 i に対して以下を繰り返す：
  • n を 0 から 21 まで繰り返す：
    • j := 2^n − i（合計を2のべき乗にするために必要な相手の値）
    • j が count に存在する場合：
      • i と j が同じ値なら：ans := ans + count[i] × (count[i] − 1)
      • それ以外の場合：ans := ans + count[i] × count[j]
• (ans / 2) mod m を返す

最後に 2 で割っているのは、ペア (i, j) と (j, i) を2回カウントしてしまうためです。また、n の範囲を 0〜21 としているのは、典型的な制約条件下で考えられる合計値の最大が 2^21 未満に収まるためです。

実装例

以下のPythonコードで実際の動作を確認できます。

from collections import Counter

def solve(deli):
    m = 10**9 + 7
    count = Counter(deli)
    ans = 0
    for i in count:
        for n in range(22):
            j = (1<<n)-i
            if j in count:
                if i == j:
                    ans += count[i] * (count[i]-1)
                else:
                    ans += count[i] * count[j]
    return (ans // 2) % m

deli = [1,7,3,6,5]
print(solve(deli))

入力

[1,7,3,6,5]

出力

3

計算量とポイント

時間計算量は O(N × 22)（N は異なる値の種類数）、空間計算量は O(N) となります。すべてのペアを総当たりする O(N²) のアプローチと比べて大幅に高速であり、データ量が多い場合でも実用的な速度で動作します。Counter を使うことで頻度集計も簡潔に書けるため、Pythonらしい読みやすい実装になっています。