概要

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

考察

各カードには表面の値 \(F_i\) と裏面の値 \(B_i\) があります。最初は全てのカードが表面を向いており、そこからちょうど \(K\) 枚のカードを裏返すことで、表に見える値の合計を最大化するのが目的です。

単純な方法として、全ての \(K\) 枚のカードの選び方を試すことが考えられます。しかし、\(N\) が最大 \(20\) なので、組み合わせの数 \({}_N C_K\) は高々 \(20\) 枚から選ぶ組み合わせでも十分小さく、全探索が可能です。

例えば、\(i\) 番目のカードを裏返すと、得られるスコア変化は \(B_i - F_i\) となります。つまり、裏返すことによる「利益」を計算して、利益が高い上位 \(K\) 個を選ぶのが最適そうに見えますが、この方法は必ずしも正しいとは限りません（特に \(K=0\) の場合や、利益がマイナスの場合など）。そのため、安全かつ確実な方法として、すべての組み合わせを試すのが良いでしょう。

アルゴリズム

1. 全てのカードについて、表面の値 \(F_i\) と裏面の値 \(B_i\) を読み込む。
2. \(N\) 枚の中から \(K\) 枚を選ぶすべての組み合わせに対して以下を行う：
   • 選ばれたカードについては裏面の値 \(B_i\) を、そうでないカードについては表面の値 \(F_i\) を加算していく。
   • 合計値を記録し、これまでの最大値と比較して更新する。
3. 最大値を出力する。

具体的には、Python の itertools.combinations を使って、\(0\) から \(N-1\) までのインデックスから \(K\) 個選ぶ全ての組み合わせを生成します。

たとえば、カードが3枚あって、カード情報が (3, 5), (2, 8), (4, 1) で \(K = 2\) のとき： - カード0と1を選ぶ：\(5 + 8 + 4 = 17\) - カード0と2を選ぶ：\(5 + 2 + 1 = 8\) - カード1と2を選ぶ：\(3 + 8 + 1 = 12\)

この中で最大は \(17\) になります。

計算量

• 時間計算量: \(O\left(\binom{N}{K} \cdot N\right)\)
  組み合わせの個数 \(\binom{N}{K}\) に対して、それぞれ \(N\) 回のループが必要です。
• 空間計算量: \(O(N)\)
  入力カード情報を保存するために \(O(N)\) 必要です。

制約より \(N \leq 20\) なので、最悪でも \(\binom{20}{10} \approx 184756\) 通りとなり、十分高速に動作します。

実装のポイント

• combinations(range(N), K) を使うことで、\(K\) 枚のカードの選び方を簡単に列挙できる。

• 各組み合わせごとに、選ばれたかどうかを判定して、表面または裏面の値を足す処理を行う。

• 最初に全てのカードを表面として扱い、その後選んだものだけ裏に切り替える方が実装しやすい。

  ソースコード

from itertools import combinations

N, K = map(int, input().split())
cards = [tuple(map(int, input().split())) for _ in range(N)]

max_sum = 0

for selected_cards in combinations(range(N), K):
    current_sum = 0
    for i in range(N):
        if i in selected_cards:
            current_sum += cards[i][1]  # 裏面
        else:
            current_sum += cards[i][0]  # 表面
    max_sum = max(max_sum, current_sum)

print(max_sum)

---

この解説は qwen3-coder-480b によって生成されました。