概要

\(N\) 枚のカードからちょうど \(K\) 枚を選んで裏返し、すべてのカードの見えている面の数値の合計を最大化する問題です。

考察

重要な気づき

各カードについて、裏返すか裏返さないかの2択があります。裏返す場合は裏面の値 \(B_i\) が、裏返さない場合は表面の値 \(F_i\) が合計に加算されます。ただし、裏返すカードはちょうど \(K\) 枚でなければなりません。

素朴なアプローチで十分か？

\(N\) 枚の中から \(K\) 枚を選ぶ組み合わせの数は \(\binom{N}{K}\) 通りです。\(N \leq 20\) なので、最大でも \(\binom{20}{10} = 184,756\) 通り程度です。各組み合わせに対して合計値を計算するのに \(O(N)\) かかりますが、全体でも数百万回程度の演算で済むため、全探索で十分間に合います。

具体例

例えば \(N = 3, K = 1\) で、カードが \((F, B) = (10, 5), (3, 8), (7, 7)\) の場合：

• カード1を裏返す → \(5 + 3 + 7 = 15\)
• カード2を裏返す → \(10 + 8 + 7 = 25\) ← 最大
• カード3を裏返す → \(10 + 3 + 7 = 20\)

このように、\(K\) 枚の選び方をすべて試して最大値を求めます。

アルゴリズム

1. \(N\) 枚のカードの情報を読み込む。
2. \(N\) 枚の中から \(K\) 枚を選ぶ全組み合わせを列挙する（Pythonの itertools.combinations を使用）。
3. 各組み合わせについて、選ばれたカードは裏面の値 \(B_i\) を、それ以外は表面の値 \(F_i\) を足し合わせて合計値を計算する。
4. すべての組み合わせの中で合計値が最大のものを出力する。

計算量

• 時間計算量: \(O(\binom{N}{K} \cdot N)\)
  • 組み合わせの数 \(\binom{N}{K}\) は最大で \(\binom{20}{10} = 184,756\)、各組み合わせに対して \(O(N)\) で合計を計算するため、最大でも約 \(184,756 \times 20 \approx 3.7 \times 10^6\) 回程度の演算で十分高速です。
• 空間計算量: \(O(N)\)
  • カード情報の保持と、裏返すカードの集合の保持に \(O(N)\) が必要です。

実装のポイント

• itertools.combinations(range(N), K) を使うと、\(0\) から \(N-1\) のインデックスから \(K\) 個を選ぶ全組み合わせを簡潔に列挙できます。

• 裏返すカードのインデックスを set に変換することで、各カードが裏返されたかどうかの判定を \(O(1)\) で行えます。

• 初期値を -float('inf') にしていますが、\(K = 0\) の場合も combinations(range(N), 0) は空タプル1つを返すため、正しく動作します。

  ソースコード

from itertools import combinations

N, K = map(int, input().split())
cards = []
for _ in range(N):
    f, b = map(int, input().split())
    cards.append((f, b))

ans = -float('inf')
for flipped in combinations(range(N), K):
    flipped_set = set(flipped)
    total = 0
    for i in range(N):
        if i in flipped_set:
            total += cards[i][1]
        else:
            total += cards[i][0]
    ans = max(ans, total)

print(ans)

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