ABC358-C

bit全探索の基礎が詰まった問題

*bit全探索

N 個のものからいくつかのものを選ぶ 2 ＾N通りが 0 以上 2 ＾N−1 以下の整数と一対一に対応するので、選び方を全探索する代わりに整数の方を全探索すればよい（そしてこれは簡単な for 文で実現できる）というものである。

(最小値を最初から考えるのではなく、全てのやり方を試したうえで最小の値を出力するってこと)

https://scrapbox.io/files/666d9e508effe6001c7b7438.png

ビットシフトによる全探索で、店の数がNと決まっている問題なので

・bit >> i は bit を i ビット右シフトし、& 1 で最下位ビット(二進数で最も一番右にあるbit)が1かどうかをチェックしする。

・もし 1 なら、その売り場 i は選ばれている。

（&1によるbit演算で、i軒目に行くかどうかを判定

(110000を何桁目を考えたいか、を基にビットシフトした後、000001と&すればその桁数の数字が1か0かどうかだけを抜き出せる)

という手順を踏む。）

for文ループ2回によって桁数上からと桁数下から挟み撃ちを行い、考えたい桁数だけを残す

もし、all_existがtrueならば、ansをcntとansに更新する。

問題文の条件より、答えはたかだかnなのでnと小さい方を出力する、という形をとっている。