概要

\(N\) 枚のカードから2枚以上を選び、選んだカードの表面の積と裏面の積が等しくなる組合せが存在するかを判定し、存在するなら最小枚数を求める問題です。

考察

問題の言い換え

各カード \(i\) について、表面の値 \(P_i\) と裏面の値 \(Q_i\) の「比」\(\frac{P_i}{Q_i}\) を考えます。選んだカードの表面の積と裏面の積が等しいということは、

\[\prod_{i \in S} P_i = \prod_{i \in S} Q_i \iff \prod_{i \in S} \frac{P_i}{Q_i} = 1\]

と言い換えられます。つまり、選んだカードの比の積が1になる部分集合を探す問題です。

制約の確認

\(N \leq 22\) という制約に注目します。全ての部分集合を列挙すると \(2^{22} \approx 4 \times 10^6\) 通りあり、これは十分に高速に処理できます。

ただし、今回のコードでは「小さいサイズから順に」調べることで、条件を満たす最小の \(|S|\) を見つけた時点で即座に終了しています。これにより、最悪ケースでは全部分集合を調べますが、\(N = 22\) でも十分間に合います。

積のオーバーフローについて

\(P_i, Q_i \leq 100\) で最大22枚選ぶため、積は最大 \(100^{22} = 10^{44}\) になりますが、Python は多倍長整数を標準でサポートしているため、オーバーフローの心配はありません。

アルゴリズム

1. カードのサイズ \(k\) を \(2, 3, \ldots, N\) の順に小さい方から試す。
2. 各サイズ \(k\) について、\(N\) 枚から \(k\) 枚を選ぶ全ての組合せを列挙する。
3. 各組合せに対して、表面の積 \(\prod P_i\) と裏面の積 \(\prod Q_i\) を計算し、等しいか判定する。
4. 等しい組合せが見つかった時点で \(k\) を出力して終了する。
5. 全てのサイズを試しても見つからなければ -1 を出力する。

具体例: カードが \((P_1, Q_1) = (2, 3)\), \((P_2, Q_2) = (3, 2)\) の場合、2枚選ぶと表面の積は \(2 \times 3 = 6\)、裏面の積は \(3 \times 2 = 6\) で等しいので、答えは \(2\) です。

計算量

• 時間計算量: \(O\left(\sum_{k=2}^{N} \binom{N}{k} \cdot k\right) = O(N \cdot 2^N)\)
  • 全部分集合（サイズ2以上）を列挙し、各組合せについて \(k\) 回の乗算を行います。\(N = 22\) のとき約 \(9 \times 10^7\) 程度の演算となり、十分間に合います。
• 空間計算量: \(O(N)\)
  • カード情報の保持と、組合せ生成に必要な空間のみです。

実装のポイント

• 小さいサイズから探索: range(2, N+1) で小さい \(k\) から順に調べることで、最初に見つかった解が自動的に最小枚数になります。見つかり次第 return で即座に終了できます。

• Python の itertools.combinations: \(N\) 個の要素から \(k\) 個を選ぶ全組合せを簡潔に列挙でき、実装が非常にシンプルになります。

• Python の多倍長整数: 積が非常に大きくなり得ますが、Python では整数のオーバーフローがないため、特別な処理は不要です。

  ソースコード

from itertools import combinations

def solve():
    N = int(input())
    cards = []
    for _ in range(N):
        p, q = map(int, input().split())
        cards.append((p, q))
    
    for size in range(2, N + 1):
        for combo in combinations(range(N), size):
            prod_p = 1
            prod_q = 1
            for i in combo:
                prod_p *= cards[i][0]
                prod_q *= cards[i][1]
            if prod_p == prod_q:
                print(size)
                return
    
    print(-1)

solve()

この解説は claude4.6opus-thinking によって生成されました。