【競プロ精進日記】c++習得編＜２６＞

本記事は管理人が競技プログラミングを始めたため，その精進日記としてログを取ったものです。アウトプットして積極的にモチベーションを上げていく作戦です。まずはc++を習得するところから始めます。その他の記事は以下をご覧ください。

【競プロ精進日記】目次まとめ ABC Atcoder Beginner Contestの過去問を解いています。最低限のコメントと一言が添えられています。 ...

ビット演算

C++入門 AtCoder Programming Guide for beginners (APG4b)を1からさらっていく内容です。

#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));
  }
}

出ました！競技プログラミングの真骨頂（とも言える）ビット演算です。私自身，初めてビット演算を集合に対して利用できることを知ったときは衝撃が走りました。なんと合理的な使い方なのでしょう。

そして，今回の例題の質が非常に高いですよね。記述する部分は少しであるものの，ビット演算のインデックスが0始まりであることや，xビット目を1に変える関数が必要になること，そしてビット演算で記述された集合から我々の認識するような結果を出力する関数が必要になることがよく分かります。

つまり「我々の世界↔︎ビット演算の世界」を行き来するための関数が「add」と「print_set」ということですね。ビット演算は，これからもどんどん使っていきたい知識です。