そのうち誰かの役に立つ

もしくは誰の役にも立たない

BitSet

アルゴリズムとデータ構造 BitSet Go

概要

  • あるパラメータをとったときの状態が2値で表せる
  • 更新処理が比較的単純な論理演算で表せる
  • 連続する複数の値を同時に更新できる

上記のようなDPをするときに、いくつかのbitをまとめて数値として計算してしまうことで高速化する、いわゆる定数倍高速化テクニック

実装

  • NewBitSet(N) で N 要素を扱えるBitSetを作成する
  • And(), Or(), Xor() で2つのBitSetのAND/OR/XOR演算を実行する
  • Lsh(N), Rsh(N) で N bit左/右シフトする
  • ShiftOr(N) で元の値と、元の値を N bit左シフトしたものの論理和を出力する
    • ある値を部分集合の和で作れるか、などの計算で使える
  • Set(N, b) で N bit目の値を b = 1\;\mathrm{or}\;0 にする
  • Get(N) で N bit目の値を取得する
  • 良い感じの例題を作るのが難しかったので、ライブラリ部分だけ記載

Python3で実装するしない

  • そもそもPythonはこういうところを頑張るような言語ではない（※個人の感想です）
  • 必要が生じたときは記事を更新する

Goで実装する

Powered by OnlineGDB