概要

\(N\)枚のカードから\(K\)枚を選んで裏返すことで、見えている面の数字の合計を最大化する問題です。

考察

各カードについて「表を向ける」か「裏を向ける」かの2択ですが、裏返す枚数がちょうど\(K\)枚という制約があります。\(N\)が最大20と小さいため、全てのカードの裏返し方を全探索することが可能です。ビット全探索を使うと、各ビットがカードの状態（0:表、1:裏）を表すことで、全ての組み合わせを効率的に調べられます。

アルゴリズム

1. \(0\)から\(2^N - 1\)までの全てのビットマスクを生成
2. 各ビットマスクについて、立っているビットの数（裏返す枚数）をカウント
3. 裏返す枚数が\(K\)と一致する場合のみ、合計値を計算
   • ビットが立っているカード：裏面の値\(B_i\)を加算
   • ビットが立っていないカード：表面の値\(F_i\)を加算
4. 全ての有効な組み合わせの中での最大合計値を出力

計算量

• 時間計算量: \(O(2^N \cdot N)\)
• 空間計算量: \(O(N)\)

実装のポイント

• ビット演算を用いて各カードの状態を効率的にチェック

• bin(bit).count('1')でビットの立っている数をカウント

• 最初にansを十分小さい値で初期化することで、最大値更新を安全に行える

  ソースコード

def main():
    import sys
    input = sys.stdin.read
    data = input().split()
    
    n = int(data[0])
    k = int(data[1])
    cards = []
    index = 2
    for i in range(n):
        f = int(data[index])
        b = int(data[index+1])
        index += 2
        cards.append((f, b))
    
    ans = -10**9
    for bit in range(1 << n):
        cnt = bin(bit).count('1')
        if cnt != k:
            continue
        total = 0
        for i in range(n):
            if bit & (1 << i):
                total += cards[i][1]
            else:
                total += cards[i][0]
        ans = max(ans, total)
    
    print(ans)

if __name__ == "__main__":
    main()

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