Aizu Online Judge（AOJ）が提供している「プログラミング応用」（ITP2）の10_D問題をC++で解いてみました。
ITP2では、「プログラミングのための基礎ライブラリを獲得します」とあります。トピック#10では、ビットセットI（bitset）を学びます。
問題（10_D: Bit Mask）
問題はリンク先をご覧ください。
bitset クラスについて学びます。
bitset クラスについて
以下は、cpprefjp 様の記事を参考にさせていただきました。
今回使う bitset クラスの演算子は、10_A で紹介しています。
C++ プログラム例（ITP2 10_D）
10_C は、ひとつのフラグについて処理をしました。この問題では、N 個の64ビットマスクを取り扱います。N 個のビットマスク値は先に読み込んでおきます（13－23行）。
操作対象のデータは、64ビット2進数と考えます。初期値は0とします。
操作対象に対して、以下の操作を行います。
- test(i)：i番目のフラグの状態がONの場合1、OFFの場合0を出力する。
- set(m)：maskm が表すフラグをまとめてONにする。マスク値とのビットORを計算します。
- clear(m)：maskm が表すフラグをまとめてOFFにする。マスク値の反転値とのビットANDを計算します。
- flip(m)：maskm が表すフラグをまとめて反転する。マスク値とのビット排他的ORを計算します。
- all(m)：maskm が表す全てのフラグがONになっている場合1、なっていない場合0を出力する。
- any(m)：maskm が表すいずれかのフラグがONになっている場合1、なっていない場合0を出力する。
- none(m)：maskm が表す全てのフラグがOFFになっている場合1、なっていない場合0を出力する。
- count(m)：maskm が表す部分のONになっているフラグの数を出力する。
- val(m)：maskm が表す部分の整数値を出力する（64ビット整数に変換して出力する）。
この問題では、bitset クラスのメソッドではなく、マスク値とのビット計算により処理をする場合が多くなります。それぞれのクエリの中心的な処理を行うコードの背景色を変更しました。
#include <iostream>
#include <bitset>
#include <vector>
using namespace std;
int main()
{
int n;
cin >> n;
bitset<64> x(0ULL);
bitset<64> zero(0ULL);
vector<bitset<64>> mask(n);
for (int i = 0; i < n; ++i) {
mask[i] = zero;
int k;
cin >> k;
for (int j = 0; j < k; ++j) {
int b;
cin >> b;
mask[i].set(b);
}
}
int q;
cin >> q;
for (int j = 0; j < q; ++j) {
int command;
cin >> command;
int i;
int m;
switch (command){
case 0:
cin >> i;
if (x.test(i)) {
cout << 1 << endl;
} else {
cout << 0 << endl;
}
break;
case 1:
cin >> m;
x = x | mask[m];
break;
case 2:
cin >> m;
x = x & ~mask[m];
break;
case 3:
cin >> m;
x = x ^ mask[m];
break;
case 4:
cin >> m;
if ((x & mask[m]) == mask[m]) {
cout << 1 << endl;
} else {
cout << 0 << endl;
}
break;
case 5:
cin >> m;
if ((x & mask[m]) != zero) {
cout << 1 << endl;
} else {
cout << 0 << endl;
}
break;
case 6:
cin >> m;
if ((x & mask[m]) == zero) {
cout << 1 << endl;
} else {
cout << 0 << endl;
}
break;
case 7:
cin >> m;
cout << (x & mask[m]).count() << endl;
break;
case 8:
cin >> m;
cout << (x & mask[m]).to_ullong() << endl;
break;
default:
break;
}
}
return 0;
}上記プログラムは、AOJ で「AC（Accepted＝正解）」と判定されました。
最後に
トピック#10 を通じて、bitset クラスについて学びました。この問題では、bitset クラスに対してマスク値を使ったビット演算を行いました。このビット演算の考え方は bitset クラスよりも幅広く使われます。
引き続き、ITP2 の問題を紹介していきます。
