AtCoder が提供しているABC（AtCoder Beginner Contest）358 C問題をC++とPythonで解いてみました。ABC358は、2024年6月15日21:00に実施されました。
AtCoder の紹介はこちらに、プログラミングの方針はこちらに記事があります。
C問題 Popcorn（Difficulty : 273）
問題の詳細は、リンク先をご覧ください。
どのポップコーン売り場で買うか全探索します。AtCoder Problems による Difficulty は 273 でした。
解答案
ポップコーン売り場の数 $N$ の上限は、10 です。このため、すべてのポップコーン売り場の組み合わせ（最大 $2^{10}$ 通り）について調べることができます。bit全探索という方法を使います。
C++ プログラム例（ABC358C）
コードの補足をします。
- 変数 bit を 0 から $2^N$ 未満まで調べます。この値が、ポップコーン売り場の組み合わせを表します。
- 下位 i ビット目が 1 であれば、i 番目のポップコーン店で購入します。
- 変数 bit から、購入するポップコーン店が決まります。その店の組み合わせで、すべての味が購入できるかを調べます。それぞれの店の味をビットORで計算して、$M$ ビットがすべてセットされているか確認します（17ー31行目）。
- 店の数（ビットの立っている数）の最小値を出力します。
以下が、C++プログラムです。bit全探索のポイントとなる行の背景行を変更しました。
#include <bits/stdc++.h>
using namespace std;
typedef unsigned int uint;
int main()
{
int n, m;
cin >> n >> m;
vector<string> s(n);
for (int i = 0; i < n; ++i) {
cin >> s[i];
}
int result = n;
for (uint bit = 0; bit < (1 << n); ++bit) {
uint t = 0;
int bit_i = 0;
for (int i = 0; i < n; ++i) {
if ((bit & (1 << i)) != 0) {
++bit_i;
for (int j = 0; j < m; ++j) {
if (s[i][j] == 'o') {
t |= 1 << j;
}
}
}
}
if (t == ((1 << m) - 1)) {
result = min(result, bit_i);
}
}
cout << result << endl;
return 0;
}AC（Accepted＝正しいプログラム）と判定されました。
Python プログラム例（ABC358C）
Python版も基本的な考え方は同じです。以下がプログラムです。
"""AtCoder Beginner Contest 358 C"""
n, m = map(int, input().split())
s = [input() for i in range(n)]
result = n
for bit in range(1 << n):
t = 0
bit_i = 0
for i in range(n):
if (bit & (1 << i)) != 0:
bit_i += 1
for j, ch in enumerate(s[i]):
if ch == 'o':
t |= 1 << j
if t == (1 << m) - 1:
result = min(result, bit_i)
print(result)こちらも「AC」と判定されました。
最後に
bit全探索を使う典型的な問題でした。タグ「bit全探索」で類題を探すことができます。
引き続き ABC の問題を紹介していきます。
