Bit全探索 ABC374 C - Separated Lunch を理解し忘れないようにする

https://atcoder.jp/contests/abc374/tasks/abc374_c

記事にする目的

• コンテストではこちらの問題はACできたが、bit全探索を用いた問題は個人的に忘れやすいので記事化をして取り出し可能な状態にしたい。

対象読者

• bit全探索が何をやっているのかある程度理解している方
• シフト演算について理解している方
• atcoderのレートが400までの方

問題概要

キーエンス本社に勤務する人数が増えてきたので、本社に存在する部署を 2 つのグループに分け、昼休みの時間帯を分けることにした。
キーエンス本社には N 個の部署が存在し、i 番目 (1≤i≤N) の部署に所属する人数は Ki人です。
グループ A に割り当てられた部署に所属する人数の合計とグループ B に割り当てられた部署に所属する人数の合計 のうち大きい方の値としてあり得る最小の値を求めてください。

方針

まず、グループA,Bをbit全探索を用いることはNの成約が小さいこともありすぐに分かった。ただ、以下の問題文がややわかりづらい。

グループ A に割り当てられた部署に所属する人数の合計とグループ B に割り当てられた部署に所属する人数の合計 のうち大きい方の値としてあり得る最小の値を求めてください。

こちらを自然言語化すると以下になる。

1. 答え用の変数を用意し、初期値を$10^{18}$(long longの上限値)とする。
2. グループA,Bで休憩時間を分けた際の合計人数をそれぞれ求める。
3. 2で求めた合計人数のうち、大きい方を求める。
4. 1の答え用の変数と3の変数で小さい方求める。bit全探索終了までこれを繰り返し、答えを出力する。

回答コード

https://atcoder.jp/contests/abc374/submissions/58459202

int main()
{
  int n;
  cin >> n;
  vector<int> k(n);

  rep(i,n) cin >> k[i];

  ll total = 1e18+1;

  // ビット全探索
  for (int bit = 0; bit < (1 << n); bit++)
  {
    ll a_sum = 0;
    ll b_sum = 0;

    for (int i = 0; i < n; i++)
    {
      // グループA
      if (bit & (1 << i))
      {
        a_sum += k[i]; 
      }
      // グループB
      else
      {
        b_sum += k[i];
      }
    }

    // 2つのグループの合計のうち大きい方の値を求める
    ll max_group_sum = max(a_sum, b_sum);
    total = min(total, max_group_sum);
  }
  cout << total << endl;
  return 0;
}