AtCoder が提供しているABC（AtCoder Beginner Contest）356 C問題をC++とPythonで解いてみました。ABC356は、2024年6月1日21:00に実施されました。
AtCoder の紹介はこちらに、プログラミングの方針はこちらに記事があります。
C問題 Keys（Difficulty : 568）
問題の詳細は、リンク先をご覧ください。
bit全探索を用いて、すべての鍵の組み合わせを試します。AtCoder Problems による Difficulty は 568 でした。
解答案
鍵の数 $N$ は、最大で15本です。$N$ が最大でも、$2^{15}=32768$ 通りであるため、すべての組み合わせを調べることができます。bit全探索と呼ばれる方法です。タグ「bit全探索」でこの手法を使う問題を紹介しています。
以下は、手法の特徴が分かりやすい類題です。
この問題では、変数 bit の下から $i$ bit目が1であれば、その鍵を正しい鍵とします。0であれば、ダミーの鍵です。
この変数 bit に対して、$M$ 個の条件が矛盾しなければ、正しい組み合わせとなります。矛盾するとは、以下の条件が成立することです。
- K 本以上の正しい鍵が選ばれているのに、ドアが開かない。
- K 本未満の正しい鍵しか選ばれていないのに、ドアが開いた。
C++ プログラム例（ABC356C）
上で説明したbit全探索を実装します。
入力は1行に複数の情報が含まれています。$i$ 番目のテストで使う鍵の個数 c を読み、その鍵の組 a[i] と、結果 r[i] を格納します。
変数 bit は、0 から $2^N – 1$ を正しい鍵の組み合わせとして調べます。
- それぞれのテストケースで該当する鍵の数 tk を求めます。
- 上記で考察した2つの条件に矛盾しないか判定します。
- すべてのテストケースで矛盾しなければ、解答となる変数 result を増やします。
以下が、C++プログラムです。bit全探索のポイントになる行の背景色を変更しました。
#include <bits/stdc++.h>
using namespace std;
typedef unsigned int uint;
int main()
{
int n, m, k;
cin >> n >> m >> k;
vector<vector<int>> a(m);
vector<bool> r(m);
for (int i = 0; i < m; ++i) {
int c;
cin >> c;
a[i].assign(c, 0);
for (int j = 0; j < c; ++j) {
cin >> a[i][j];
--a[i][j];
}
char ch;
cin >> ch;
if (ch == 'o') {
r[i] = true;
} else {
r[i] = false;
}
}
int result = 0;
for (uint bit = 0; bit < (1 << n); ++bit) {
bool t = true;
for (int i = 0; i < m; ++i) {
int tk = 0;
for (int j = 0; j < a[i].size(); ++j) {
if ((bit & (1 << a[i][j])) != 0) {
++tk;
}
}
if (((tk >= k) && !r[i])) {
t = false;
}
if (((tk < k) && r[i])) {
t = false;
}
}
if (t) {
++result;
}
}
cout << result << endl;
return 0;
}AC（Accepted＝正しいプログラム）と判定されました。
Python プログラム例（ABC356C）
Python版も基本的な考え方は同じです。以下がプログラムです。
"""AtCoder Beginner Contest 356 C"""
n, m, k = map(int, input().split())
a = [[] for _ in range(m)]
r = [False] * m
for i in range(m):
c_a_r = input().split()
c = int(c_a_r[0])
for j in range(c):
a[i].append(int(c_a_r[1 + j]) - 1)
if c_a_r[-1] == 'o':
r[i] = True
else:
r[i] = False
result = 0
for bit in range(1 << n):
t = True
for i in range(m):
tk = 0
for j in range(len(a[i])):
if (bit & (1 << a[i][j])) != 0:
tk += 1
if tk >= k and not r[i]:
t = False
if tk < k and r[i]:
t = False
if t:
result += 1
print(result)こちらも「AC」と判定されました。
最後に
bit全探索という定番の考え方を用いて、問題を解くことができました。
引き続き ABC の問題を紹介していきます。
