概要

\(N\) 枚のカードの中から2枚以上を選び、選んだカードの「表面に書かれた整数の積」と「裏面に書かれた整数の積」が等しくなるような選び方のうち、選んだ枚数の最小値を求める問題です。

考察

カードの選び方は「選ぶ」か「選ばない」かの2通りあるため、すべての選び方を単純に全探索すると \(2^N\) 通りになります。制約の \(N \le 22\) では、最大で \(2^{22} \approx 4.2 \times 10^6\) 通りとなり、Pythonなどの言語では実行時間制限（TLE）に引っかかる可能性があります。

そこで計算量を劇的に減らす手法である 半分全列挙（Meet-in-the-Middle） を使用します。

問題の条件である「表面の積と裏面の積が等しい」という式は、比の形で表すと以下のようになります。 $\( \frac{\prod P_i}{\prod Q_i} = 1 \)$

ここで、選んだカードを前半グループ \(A\) と後半グループ \(B\) に分けます。それぞれのグループから選んだカードの積の比を \(\frac{p_A}{q_A}\)、\(\frac{p_B}{q_B}\) とすると、条件は次のように変形できます。 $\( \frac{p_A}{q_A} \times \frac{p_B}{q_B} = 1 \iff \frac{p_A}{q_A} = \frac{q_B}{p_B} \)$

つまり、前半と後半でそれぞれすべての選び方を試し、「表の積と裏の積の比（既約分数）」を計算しておきます。そして、前半の比が \(p : q\) のとき、後半で比が \(q : p\) となる選び方 があれば、それらを組み合わせることで条件を満たすことができます。

アルゴリズム

1. 前処理 各カードの \(P_i, Q_i\) をあらかじめ最大公約数（GCD）で割り、互いに素な状態（既約分数）にしておきます。これにより、計算途中の数値が大きくなるのを防ぎます。
2. グループ分け \(N\) 枚のカードを、前半（\(\lfloor N/2 \rfloor\) 枚）と後半（残りの枚数）の2つのグループに分けます。
3. 前半グループの全列挙 前半グループのすべての部分集合（空集合を除く）について、選んだカードの表の積 \(p\) と裏の積 \(q\) を計算し、GCDで割って比 \((p, q)\) を求めます。
   • もし比が \((1, 1)\) で、かつ 選んだ枚数が2枚以上 なら、答えの候補（最小枚数）を更新します。
   • 辞書（ハッシュマップ）に、比 \((p, q)\) をキーとして、その比を作るのに必要な「最小の枚数」を記録します。
4. 後半グループの全列挙 後半グループについても同様に全列挙を行い、辞書を作成し、条件を満たす場合は答えの候補を更新します。
5. 前半と後半の組み合わせ 前半の辞書に記録された各比 \((p, q)\) について、後半の辞書に逆の比 \((q, p)\) が存在するかを調べます。存在する場合、それらを組み合わせると全体の比が \(1:1\) になります。選んだ枚数は「前半の枚数 ＋ 後半の枚数」となるため、これが現在の最小値より小さければ答えを更新します。 （前半と後半から少なくとも1枚ずつ選ぶため、合計枚数は必ず2枚以上になります）
6. 結果の出力 最終的な最小値が初期値から更新されていればその値を出力し、そうでなければ -1 を出力します。

計算量

• 時間計算量: \(O(2^{N/2} \log(\text{積の最大値}))\) \(N \le 22\) を半分にするため、探索する状態数はそれぞれ最大 \(2^{11} = 2048\) 通りとなります。各状態でのGCD計算や辞書の参照を含めても非常に高速に動作し、余裕で実行時間制限に間に合います。
• 空間計算量: \(O(2^{N/2})\) 前半と後半の計算結果を保存する辞書の要素数は、最大でも \(2^{11}\) 個程度であり、メモリ使用量もごくわずかです。

実装のポイント

• 「2枚以上」という条件の扱い 1枚だけ選んで \(P_i = Q_i\) となるケースは、問題の「2枚以上選ぶ」という条件に違反します。そのため、前半のみ・後半のみで比が \(1:1\) になるケースを判定する際は、c >= 2（選んだ枚数が2枚以上）であることを必ずチェックする必要があります。

• 既約分数での管理 比を浮動小数点数（float）で管理すると誤差が発生する可能性があるため、必ず整数のペア (p // g, q // g) として辞書のキーに持たせるのが安全です。

  ソースコード

import sys
from math import gcd

def solve():
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    N = int(input_data[0])
    A = []
    B = []
    idx = 1
    for i in range(N):
        p = int(input_data[idx])
        q = int(input_data[idx+1])
        idx += 2
        g = gcd(p, q)
        if i < N // 2:
            A.append((p // g, q // g))
        else:
            B.append((p // g, q // g))
            
    ans = float('inf')
    
    half1 = {}
    for i in range(1, 1 << len(A)):
        p, q = 1, 1
        c = 0
        for j in range(len(A)):
            if (i >> j) & 1:
                p *= A[j][0]
                q *= A[j][1]
                c += 1
        g = gcd(p, q)
        p //= g
        q //= g
        if p == 1 and q == 1 and c >= 2:
            if c < ans:
                ans = c
        if (p, q) not in half1 or c < half1[(p, q)]:
            half1[(p, q)] = c

    half2 = {}
    for i in range(1, 1 << len(B)):
        p, q = 1, 1
        c = 0
        for j in range(len(B)):
            if (i >> j) & 1:
                p *= B[j][0]
                q *= B[j][1]
                c += 1
        g = gcd(p, q)
        p //= g
        q //= g
        if p == 1 and q == 1 and c >= 2:
            if c < ans:
                ans = c
        if (p, q) not in half2 or c < half2[(p, q)]:
            half2[(p, q)] = c

    for (p, q), c1 in half1.items():
        if (q, p) in half2:
            c2 = half2[(q, p)]
            if c1 + c2 < ans:
                ans = c1 + c2
                
    if ans == float('inf'):
        print(-1)
    else:
        print(ans)

if __name__ == '__main__':
    solve()

この解説は gemini-3.1-pro-thinking によって生成されました。