zukaついに競技プログラミングを始めました！
本記事は，管理人の競技プロ精進日記としてログを取ったものです。モチベーションを爆上げするために，積極的にアウトプットしていく作戦です。これから競技プログラミングを始めようと考えている人や，なんとなく敷居が高いと感じている人の参考になれば嬉しく思います。その他の記事は以下をご覧ください。
目次
本記事の概要
Atcoderが公表しているc++の入門記事の内容を1からさらっていくものです。今回は3.05.ビット演算です。
実装
#include <bits/stdc++.h>
#define _GLIBCXX_DEBUG
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
using namespace std;
// AとBに共通して含まれる要素からなる集合を返す
bitset<50> intersection(bitset<50> A, bitset<50> B) {
return A & B;
}
// AとBのうち少なくとも一方に含まれる要素からなる集合を返す
bitset<50> union_set(bitset<50> A, bitset<50> B) {
return A | B;
}
// AとBのうちどちらか一方にだけ含まれる要素からなる集合を返す
bitset<50> symmetric_diff(bitset<50> A, bitset<50> B) {
return A ^ B;
}
// Aから値xを除く
bitset<50> subtract(bitset<50> A, int x) {
return A.reset(x);
}
// Aに含まれる要素に1を加える(ただし、要素49が含まれる場合は0になるものとする)
bitset<50> increment(bitset<50> A) {
if (A.test(49)){
A = A << 1;
A.set(0);
}
else{
A = A << 1;
}
return A;
}
// Aに含まれる要素から1を引く(ただし、要素0が含まれる場合は49になるものとする)
bitset<50> decrement(bitset<50> A) {
if (A.test(0)){
A = A >> 1;
A.set(49);
}
else{
A = A >> 1;
}
return A;
}
// Sに値xを加える
bitset<50> add(bitset<50> S, int x) {
S.set(x, 1); // xビット目を1にする
return S;
}
// 集合Sの内容を昇順で出力する(スペース区切りで各要素の値を出力する)
void print_set(bitset<50> S) {
vector<int> cont;
for (int i = 0; i < 50; i++) {
if (S.test(i)) {
cont.push_back(i);
}
}
for (int i = 0; i < cont.size(); i++) {
if (i > 0) cout << " ";
cout << cont.at(i);
}
cout << endl;
}
// これより下は書き換えない
int main() {
bitset<50> A, B;
int N;
cin >> N;
for (int i = 0; i < N; i++) {
int x;
cin >> x;
A = add(A, x);
}
int M;
cin >> M;
for (int i = 0; i < M; i++) {
int x;
cin >> x;
B = add(B, x);
}
// 操作
string com;
cin >> com;
if (com == "intersection") {
print_set(intersection(A, B));
} else if (com == "union_set") {
print_set(union_set(A, B));
} else if (com == "symmetric_diff") {
print_set(symmetric_diff(A, B));
} else if (com == "subtract") {
int x;
cin >> x;
print_set(subtract(A, x));
} else if (com == "increment") {
print_set(increment(A));
} else if (com == "decrement") {
print_set(decrement(A));
}
}ポイント
今回おさえるべき内容
bitsetを用いればビット演算を明示的に行うことができる
4つの基本的な演算子とシフト演算子をおさえればOK
ビット全探索でビット演算が大活躍する
競技プログラミングで最初の難関となるのが，おそらくビット操作だと思います。非情報系の方であれば，コンピュータアーキテクチャなどは履修されていない型の方が多いでしょうから，ビットに関する知識はほぼないのではないでしょうか。
全通りをしらみつぶしに調べ上げる問題などでは，各ビットをフラグと見立てて全探索を行う「ビット全探索」が大活躍します。以下のような雛形を用いることでビット全探索は実現できます。ビット数をNとします。
// 2^Nだけ繰り返す
for (int tmp = 0; tmp < (1 << N); tmp++) {
// 毎回tmpをNビット表示したsを定義する
bitset<N> s(tmp);
// 各ビットに対する処理を行う
for (int i = 0; i < N; i++) {
// もしsのiビット目が1であれば
if (s.test(i)) {
// 何かしらの処理をする
}
}
}
コメント