データの持ち方の一つにbit形式で持つものがある。それらをうまく操作するテクニックを書く。
数個前(個数無制限)の要素の和保持するタイプ
bitdpで持つ状態としてある上限を超えないぎりぎりとなるような数個手前の和となる。下の例題のままである。
この時役に立つ操作をいくつか書く。
1 << (n - 1) := nを含む
10100110 := 前に(2, 3, 1, 2)とあるとき、左にあるように、右から上のようなルールに従って、数字を追加する
//このようなルールで追加すると、bitの桁数で簡単に和がいくつかがわかる。例えば↑の例だと8桁なので、2+3+1+2=8とわかる。
//たとえば、記録する和は5までにしたい場合は、1011などに例えば100を追加するときに、次の操作をすればよい。
//そのままつけると、1011100となるが、ここで、(1 << 5) - 1 == 11111と論理積を取れば、下五ケタを抽出することができる。
//下の数ケタだけ抽出するときは、bitmaskを作ると楽！桁あふれも考えなくてよい。（ローリングハッシュのmod(2^64)の自動であふれ出る分を無視する要領）
//また、何か所か(例として2か所)いずれかでのbitが立ってはいけない。というときは、次のようにすればよい。
int banned = (1 << i) + (1 << j);
if(bit & banned);/OUT!
else ;//SAFE!
//全部あるとダメならば条件式を
if((bit & banned) == banned);
//にすればよい。
ARC058 E(700)
この問題通りの設定である。僕の頭ではこれの応用となるほかの問題をまだ考えついてないが、出てきたら役には立ちそう。
