AtCoder が提供しているABC（AtCoder Beginner Contest）374 C問題をC++とPythonで解いてみました。ABC374は、2024年10月5日21:00に実施されました。
AtCoder の紹介はこちらに、プログラミングの方針はこちらに記事があります。
C問題 Separated Lunch（Difficulty : 226）
問題の詳細は、リンク先をご覧ください。
bit全探索を使って、すべてのグループ分けについて調べます。AtCoder Problems による Difficulty は 226 でした。
解答案
$2 \leqq N \leqq 20$ であるため、すべての人をグループAに分けるか、グループBに分けるかは、最大 $2^{20}$ 通りのあります。bit全探索ですべての場合を調べます。
C++ プログラム例（ABC374C）
bit全探索の定番コードについて解説します。
- [0, 2n) の範囲を全探索します（17行目）。
- 下から $i$ 番目のビットが0であれば、k[i] 人をグループAとします。ビットが1であれば、k[i] 人をグループBとします（20ー26行目）。
- グループAとグループBの大きい方の値の最小値を更新します（27行目）。
以下が、C++プログラムです。
#include <bits/stdc++.h>
using namespace std;
typedef unsigned int uint;
#define INF 2000000001
int main()
{
int n;
cin >> n;
vector<uint> k(n);
for (int i = 0; i < n; ++i) {
cin >> k[i];
}
uint result = INF;
for (uint bit = 0; bit < (1U << n); ++bit) {
uint a = 0;
uint b = 0;
for (int i = 0; i < n; ++i) {
if ((bit & (1U << i)) == 0) {
a += k[i];
} else {
b += k[i];
}
}
result = min(result, max(a, b));
}
cout << result << endl;
return 0;
}AC（Accepted＝正しいプログラム）と判定されました。
Python プログラム例（ABC374C）
Python版も基本的な考え方は同じです。以下がプログラムです。
"""AtCoder Beginner Contest 374 C"""
INF = 2 * 10 ** 9 + 1
n = int(input())
k = list(map(int, input().split()))
result = INF
for bit in range(1 << n):
a = 0
b = 0
for i in range(n):
if (bit & (1 << i)) == 0:
a += k[i]
else:
b += k[i]
result = min(result, max(a, b))
print(result)こちらも「AC」と判定されました。
最後に
bit全探索を使う典型問題でした。
引き続き ABC の問題を紹介していきます。
