AtCoder begginer contest 358 - c <bit全探索> （ruby）

atCoderの過去問題を解いていて、bitを利用した全探索がどうも苦手です。
理解を整理するため、忘備録として解き方及びコードの解説を残します。
※言語はrubyを用いていますが、コードの内容は公式解説動画と同じです。
また、いわゆる「rubyっぽい」コードではないです。ご留意ください。

追記分について
最初の回答コードよりわかりやすいと思われる回答を、一番下に載せています。
最初のコードが分かりにくい場合、そちらをみていただくと良いかもしれません。

問題概要

タイトル：Popcorn
ポップコーンの屋台がN個あり、全部でM個の種類がある。
しかし、屋台ごと売っている種類が違うため、可能な限り少ない回数で全ての味を買いたい。
その最小の屋台数を求める。
制約：1≤N,M≤10
どのポップコーンも、どこかしらでは売っている

ex

3 5
oooxx
xooox
xxooo

oの場合はその味を売っている。
1店舗目と3店舗目を回れば全て買えるので、2が最小となります。

回答

考察

入力のbitっぽさと、制約の小ささから、訪れる店舗の組み合わせを全探索すれば良さそう。

方針

• 店は、訪れる・訪れないの2パターンなのでビットシフトでループを回す
• それぞれの味ごと、訪れる店の組み合わせで購入できるか、を確認していく
  • もし購入できない味がある場合はスルー
  • 全て購入できる場合、訪れる店の数を確認し、最小であれば更新していく

回答

回答コード（ruby）

def popcount_kernighan(num)
  count = 0
  while num > 0
    num &= (num - 1)
    count += 1
  end
  count
end

N, M = gets.split.map(&:to_i)
shop = []
N.times { shop << gets.chomp }

ans = N
(0...(1 << N)).each do |bit|
  ok = true
  M.times do |i|
    can = false
    N.times do |j|
      if (bit>>j&1 == 1)
        can = true if shop[j][i] == 'o'
      end
    end
    ok = false if !can
  end
  ans = [ans, popcount_kernighan(bit)].min if ok
end

puts ans

コードの解説

順に追っていきます。
最初の popcount_kernighan 関数ですが、これは10進数の数字を渡すと、2進数で表した時の1の数を返してくれます。
ex: 6(10) -> 110(2) -> 1が二つなので2が得られます。

次に、入力を受け取ります。
Nが店の数、Mがポップコーンの種類数です。
shopには、お店ごと売っているポップコーンの種類が入ります。
コメントアウト部は、exでの入力値の場合を表します。

N, M = gets.split.map(&:to_i) # N=3, M=5
shop = []
N.times { shop << gets.chomp } # ["oooxx", "xooox", "xxooo"]

メインの処理に移ります。

ans = N 
(0...(1 << N)).each do |bit| 
  ok = true
  M.times do |i|
    can = false
    N.times do |j|
      if (bit>>j&1 == 1)
        can = true if shop[j][i] == 'o'
      end
    end
    ok = false if !can
  end
  ans = [ans, popcount_kernighan(bit)].min if ok
end

うーん、ぱっと見よくわからないです。もう少し細かく見ていきます。
まず、回答をN（店舗数）で初期化します。どのポップコーンもどこかしらでは売っているため、最大でNになります。
そして、ビットシフトを利用したループをしています。

ans = N 
(0...(1 << N)).each do |bit| 
    ok = true
    ~略~
end

もう少し詳細に記載します。
(0...x)という記載は、rubyのrangeオブジェクトです。
0~x-1までの範囲を持ちます。0..xとすると、0~xまでです。
そして、1<<Nについて、bitのシフト演算を利用しています。Nの数だけ左シフトしてくれます。
例：N=3の時、1<<5 = 1000(2) = 8(10) となります。
詳細は、別途解説されているサイトを確認してください。

ここで、どうしてこのシフトで全探索ができるかについて少し触れます。N=3の想定で考えます。
2進数でイメージしてみます。
1<<3 = 1000(2)です。今回は0...(1<<3)なので、これを含みません。すると、
000、001、010、011、100、101、110、111（、1000）
というように、都合よく0,1の組み合わせを全て表すことができます。
今回のような、それぞれの事象が2つのどちらか（お店に訪れた or 訪れなかった）という時に、2進数で考えると都合が良いです。
※bitには010のような二進数表記が入っているわけではなく、0,1,2と通常の数字が入ります。が、それを2進数で表せば000、001、010、のようになっています。

よって今回は、1となっている店舗を訪れた、という組み合わせの一つとしてループを回せます。
ex: 011の場合、（右から考えて）1店舗目と2店舗目を訪れた、となる
そして、その組み合わせでポップコーンが全て買えるかをokフラグで表します。trueで初期化されています。

続きます。

M.times do |i|
    can = false
    ~略~
end

さて、こちらはMでループを回しています。Mはポップコーンの種類なので、種類ごと購入できるかを確認していきます。canが購入できるかを表し、falseでの初期化です。

最後のループです。

N.times do |j|
    if (bit>>j&1 == 1)
        can = true if shop[j][i] == 'o'
    end
end
ok = false if !can

これは、「訪れるの店舗で該当の味が買えるか」を確認しています。
重要なのは以下です。

if (bit>>j&1 == 1)
    can = true if shop[j][i] == 'o'
end

ここが、何をしているかぱっと見難しく思います。順にみます。
(bit>>j&1 == 1)
これは、先ほどと逆の右シフトを利用し、その店舗を訪れたかを確認しています。
具体的に考えます。
最初のループ (0...(1 << N)).each do |bit| は、訪れた店を2進数で表したループであることを思い出します。今は011、という店舗の組み合わせで考えてみます。
jは、店舗数分だけループします。今回は0,1,2となります。
そして、<<は右シフトです。2進数にした状態から与えた数だけ右に移動してくれます。すると、
j=0 の時
bit>>j -> 011>>0 -> 011
011&1 = 011&001 = 001 = 1

j=1 の時
bit>>j -> 011>>1 -> 01
01&1 = 01&01 = 01 = 1

j=2 の時
bit>>j -> 011>>2 -> 0
0&1 = 0

となります。&はANDで、両方の同じくらいが1であれば1、そうでなければ0となります。
&1というのは、その一桁目が1であるかの確認ということです。
そして、jの数分だけ右シフトしてあるため、j+1店舗目を訪れたか、を確認できるというわけです。
そして、もし訪れていた場合、shopの該当の店をみて、そこで一個前のループで指定している種類のポップコーンが売られているか確認します。
売られていたら、canをtrueにします。
can = true if shop[j][i] == 'o'

そして、ループを抜けたあとにcanがfalseのまま（買えないまま）であれば、okをfalseにし、その組み合わせでは全ての種類を変えないよ、としてあげます。
ok = false if !can

最後に、もしokがtrueのままだった（=全ての種類が買える）場合、bitの1の数を確認し、小さい方で更新していきます。
ans = [ans, popcount_kernighan(bit)].min if ok

最後に、出力です。
puts ans

これで回答完了です。

終わりに

今回は、ビットの右シフト・左シフトが両方出てきたことや、種類でのループをするというところで、理解するのが難しかったように思います。
この解放以外にも、種類 -> お店確認 ではなく お店 -> 種類確認 での回答や、お店のポップコーン自体をbitで表す等もできそうな気がしたり。しなかったり。
色々な解放があるかと思いますので、bitになれるためにも練習していきたいなと感じております。
ありがとうございました。

20250326 追記（少し変えたver）

なかなかスムーズに解けず、何度か繰り返し解いている中、もう少し直感的にわかりやすいかもしれない回答ができたので、そちらも載せておきます。

何を変えたかというと、「すべての種類が買えるか」の判定方法です。
最初の回答では、種類ごとMのループを回し、店舗ごとNのループを回し、、という形で、その店舗の組み合わせでその種類が買えるか・買えないかという判定をしていました。

ただ、店舗における種類は、'xxooo'のようにこちらも置いてある/置いていないの2通りであるため、それもbitで表し単純にORを取っていけばいけそうではないかと思い、実装してみました。
個人的には種類のループを回すよりわかりやすい気がしています。

N, M = gets.split.map(&:to_i)
tasts = Array.new(N, 0)

def popcount(num)
  count = 0
  while num > 0
    num &= (num - 1)
    count += 1
  end
  count
end

N.times do |i|
  ta = gets.chomp.chars.reverse
  ta.each_with_index do |t, j|
    tasts[i] |= (1<<j) if t == 'o'
  end
end

ans = N
(1<<N).times do |bit|
  can_t = 0
  N.times do |i|
    can_t |= tasts[i] if (bit>>i&1 == 1)
  end
  ans = [ans, popcount(bit)].min if popcount(can_t) == M
end

puts ans

最初の回答より、個々の判定がすっきりして分かりやすい気がしますね

ans = N
(1<<N).times do |bit|
  can_t = 0
  N.times do |i|
    can_t |= tasts[i] if (bit>>i&1 == 1)
  end
  ans = [ans, popcount(bit)].min if popcount(can_t) == M
end