yukicoder No.3 ビットすごろくの解説を書いていた。それがビットに関する問題だったので、記念してこの記事を書く。
bit問題とは、基本的にはbit全探索のために使うbitと、bitの考え方を使うbitの二種類があると思っている。この記事では、主に後者をまとめることにする。
ABC-Cはbit全探索のbitしか基本的にはでないが、D以降になると後者のものも増える。
よって、ビットに関する知識はD以降の正答率を少し押し上げるはずだと思っている。
前提知識：ビット表記
そもそもの話だが、ビット表記は2進法になる。たとえば
・6は110になる
・19は10011になる
・32は100000になる
こんな感じ。
右から見てi桁目は$2^{i-1}$の位を表す。
この表記を知らないと話ができないので、先に説明した。
ビット演算子
一般的に出てくるビット演算子は3つ。&と|と$\oplus$だ。
もちろん、記号だけだとわからないと思うので、どのようなものかを説明する。
論理積
&は、論理積(AND)というものを求める記号である。
| x | y | xANDy |
|---|---|---|
| 0 | 0 | 0 |
| 0 | 1 | 0 |
| 1 | 0 | 0 |
| 1 | 1 | 1 |
こんな感じで、xとyともに1になっているもののみ1にするという記号だ。
例
・1&3=1
・3&6=2
・4&9=0
論理和
|は、論理和(OR)というものを求める記号である。
| x | y | xORy |
|---|---|---|
| 0 | 0 | 0 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 1 |
こんな感じで、xとyどちらかが1になっているものを1にするという記号だ。
例
・1|3=3
・3|6=2
・4|9=13
排他的論理和
$\oplus$は、排他的論理和(XOR)というものを求める記号である。
| x | y | xXORy |
|---|---|---|
| 0 | 0 | 0 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 0 |
こんな感じで、xとyどちらかのみ1になっているものを1にするという記号だ。
例
・1$\oplus$3=2
・3$\oplus$6=5
・4$\oplus$9=13
基本的に、bitをうんたらかんたらするタイプの問題は、上記のものを理解していれば何を言ってるかがわかるものが多い。
その他、覚えておきたいビットに関する関数
上記のものほどではないが、よく使う関数について説明する。
builtin_popcount
これはbit列に直したときに、1の出てくる数という意味である。
例
・5=101=2
・25=11001=3
・125=1111101=6
なお、一般的に問題文に出るときはpopcountと呼ばれる。
これだけである。ほかにあるのかもしれないが、基本的にこれだけ覚えておけば大半は対処できる。
C++におけるビット系の扱い方
まず、注意してほしいのが排他的論理和を求める記号が^であることだ。これさえ覚えておけば、基本的に問題はない。
ビット列を作るとき
使用例：bitset<60> $e$(50)
<>の中の数字は、作るbit列の長さについて(中の数字は常に定数でないとならない)。
ダメな例：bitset<$k$> $e$(50)
()の中には、基本的に数字を入れることで中の数字をビット列に直す。という使い方が大半。
ビット演算子について
ビット演算子は変数にも使える。これを覚えておこう。
論理積→&
論理和→&
排他的論理積→^
こういう対応をしている
builtin_popcountの使い方
ビット列eに対してe.count()で求まる。
ビット問題への考え方
D - Popcount and XOR
実行時間制限: 2 sec / メモリ制限: 1024 MB
配点 : 400 点
問題文
非負整数 $a,b,C$ が与えられます。 次の 5 つの条件をすべて満たす非負整数の組 $(X,Y)$ が存在するか判定し、存在するならひとつ出力してください。
・$0≤X<2^{60}$
・$0≤Y<2^{60}$
・$popcount(X)=a$
・$popcount(Y)=b$
・$X⊕Y=C$
ただし、⊕ はビットごとの排他的論理和を表します。
条件を満たす $(X,Y)$ が複数存在する場合、どれを出力しても構いません。
制約
$N$ は $0$ 以上 $2^{60}$ 未満の整数
$M$ は $0$ 以上 $2^{60}$ 未満の整数
ABC347-Dより
D - Masked Popcount
実行時間制限: 2 sec / メモリ制限: 1024 MB
配点 : 400 点
問題文
整数 $N,M$ が与えられるので、
$\sum_{k=0}^N$ $popcount(k$&$M)$ を $998244353$ で割った余りを求めてください。
ただし、 & はビット単位 AND 演算を表します。
制約
$N$ は $0$ 以上 $2^{60}$ 未満の整数
$M$ は $0$ 以上 $2^{60}$ 未満の整数
ABC356-Dより
このような一般にbitと絡める問題はとある事実を知るだけで見通しがかなり良くなる。それが各bitは独立しているという事実である。
ビット列の$2^3$桁目が変わっても$2^5$桁目は変わらない。その事実だ。
この考えの有効性を理解するのなら下の問題の方がいいだろう。
$M$の$2^i$桁目について考えるときに、$M$の$2^{i+1}$桁目が影響することはない。よって、各桁の解をいい感じに求めてしまえば、あとはそれを足すだけ。この考えを知っただけで、問題への感じ方がだいぶ変わっただろう。
まとめ
結果から言うと、言いたかったのは最後の独立性のみである。この考えを持っていれば、さらにビット演算の使い方を理解すれば、かなりビット演算問題も解きやすくなるのではなかろうか。