概要

N枚のカードについて、表面の数字の積と裏面の数字の積が等しくなるような2枚以上のカードの選び方が存在するか判定し、存在する場合は最小の枚数を求める問題です。

考察

制約が \(N \leq 22\) と比較的小さいため、全てのカードの組み合わせ（部分集合）を調べる方法が考えられます。各カードの表面と裏面の数字は最大100であり、積が非常に大きくなる可能性がありますが、実際には22枚選んだ場合でも最大 \(100^{22}\) という天文学的な数値になります。しかし、問題の性質上、表面と裏面の積が等しいかどうかを直接比較する必要があります。

素朴なアプローチとして、全ての部分集合（\(2^N - 1\) 通り）を調べ、表面の積と裏面の積が等しいかチェックする方法が有効です。N=22の場合、部分集合の数は約420万通りであり、これは現代のコンピュータで十分扱える範囲です。

アルゴリズム

ビットマスクを用いた全探索アルゴリズムを採用します。具体的には：

1. 0から \(2^N - 1\) までの全てのビットマスクを生成する（各ビットがカードの選択状態を表す）
2. 各ビットマスクについて、選択されたカードの数をカウントする（2枚未満はスキップ）
3. 選択されたカードの表面の数字の積と裏面の数字の積を計算する
4. 両者の積が等しい場合、現在の最小値より小さい枚数であれば更新する
5. 全ての組み合わせを調べ終えた後、条件を満たす組み合わせがあれば最小枚数を、なければ-1を出力する

計算量

• 時間計算量: \(O(2^N \cdot N)\)
  • 部分集合の数が \(2^N\) 通り
  • 各部分集合について、Nビットをチェックして積を計算する
• 空間計算量: \(O(N)\)
  • カードの情報を格納するためのメモリのみ使用

実装のポイント

• ビットマスクの各ビットがカードの選択状態に対応します（1< でi番目のカードを選択）

• 積の計算では整数のオーバーフローに注意すべきですが、Pythonは自動で多倍長整数を扱うため問題ありません

• 最小値の初期値は無限大（float('inf')）に設定し、条件を満たす組み合わせが見つかった場合のみ更新します

• 枝刈りとして、現在の最小値より多い枚数の組み合わせはスキップすることで効率化しています

  ソースコード

import sys
from math import gcd
from functools import reduce

def main():
    data = sys.stdin.read().split()
    if not data:
        print(-1)
        return
        
    n = int(data[0])
    cards = []
    index = 1
    for i in range(n):
        p = int(data[index]); q = int(data[index+1]); index += 2
        cards.append((p, q))
        
    if n < 2:
        print(-1)
        return
        
    min_size = float('inf')
    
    for bitmask in range(1, 1 << n):
        size = bin(bitmask).count('1')
        if size < 2:
            continue
            
        if size >= min_size:
            continue
            
        prod_p = 1
        prod_q = 1
        for i in range(n):
            if bitmask & (1 << i):
                prod_p *= cards[i][0]
                prod_q *= cards[i][1]
                
        if prod_p == prod_q:
            min_size = min(min_size, size)
            
    if min_size != float('inf'):
        print(min_size)
    else:
        print(-1)

if __name__ == "__main__":
    main()

この解説は deepseekv3 によって生成されました。