AtCoder ABC 374 C - Separated Lunch (3Q, 灰色, 300 点)

bit 全探索が意外と思い浮かびづらいかもしれない。

• 問題へのリンク

問題概要

個の正の整数 が与えられる。これらの整数を A, B の 2 グループに分ける。

の最大値を求めよ。

制約

• 

考えたこと

bit 全探索を使うと、 個のものに対して「0」「1」の値を割り当てる方法をすべて調べることができる。今回は

• 1：グループ A
• 0：グループ B

に分けると考えるとちょうどよい。この 通りのグループ分けをすべて試して、スコアの最大値を求めよう。なお、bit 全探索は次の記事を参照。

drken1215.hatenablog.com

計算量は となる。

コード

#include <bits/stdc++.h>
using namespace std;

int main() {
    long long N, all = 0, res = 1LL << 60;
    cin >> N;
    vector<long long> K(N);
    for (int i = 0; i < N; i++) cin >> K[i], all += K[i];

    for (int bit = 0; bit < (1<<N); bit++) {
        long long sum = 0;
        for (int i = 0; i < N; i++) if (bit & (1 << i)) sum += K[i];
        res = min(res, max(sum, all - sum));
    }
    cout << res << endl;
}