実行時間制限: 2 sec / メモリ制限: 1024 MB / Difficulty: 226

問題概要

ある会社には $N$ 個の部署が存在し、 $i$ 番目の部署に所属する人数は $K_i$ 人である。それぞれの部署をグループ $A, B$ のいずれか一方に割り当て、グループ $A$ に割り当てられた部署に所属する人数の合計とグループ $B$ に割り当てられた部署に所属する人数の合計のうち、大きい方の値としてあり得る最小の値を求めよ。

制約

入力はすべて整数。
$2 \leq N \leq 20$
$1 \leq K_i \leq 10^8$

考察

「各部署を $A, B$ どちらのグループに振り分けるのか」を考えると、あり得る組み合わせは $2^N$ 通り存在する。ここで、制約から $N \leq 20$ なので、最大でも $10^6$ 程度のパターンしかなく、これは全探索できそう。

各パターンについて、 $A, B$ に振り分けた部署の人数の総和をそれぞれ取っていき、 $\max(A, B)$ を求めて最小化していく。

実装では bit 全探索を用いるのがよいだろう。全体の計算量は $O(N \cdot 2^N)$ となる。

コード

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

using ll = long long;

#define rep(i, start, end) for (auto i = (start); (i) < (end); (i)++)

constexpr auto INFL = 1LL << 60;

template <typename T>
inline bool chmin(T &a, T b) { return ((a > b) ? (a = b, true) : (false)); }

// ======================================== //

int main()
{
    int N;
    cin >> N;
    vector<ll> K(N);
    rep(i, 0, N) cin >> K[i];

    ll ans = INFL;
    rep(bit, 0, (1 << N)) {
        ll A = 0, B = 0;
        rep(i, 0, N) {
            if (bit & (1 << i)) {
                A += K[i];
            } else {
                B += K[i];
            }
        }

        chmin(ans, max(A, B));
    }

    cout << ans << endl;
    return 0;
}