---

## ✅ ビットマスクとは？

**ビットマスク（bitmask）**とは、  
「**整数の2進数のビット（0と1）を使って、集合を表現したり操作したりするテクニック**」です。

---

このとき、集合 {1, 2, 4} を表すビット列は：

1101 （2進数）= 13（10進数）

この「13」という整数が、この集合を表す ビットマスク になります。

• 集合を 数値1つ で表現できる。
• 集合の操作（追加、削除、包含など）が ビット演算で高速にできる。
• 小さい N（~20くらい）であれば、すべての部分集合を 2^N 通りで列挙可能。

| 操作 | ビット演算 | 意味 | | --------------------------- | ------------------- | -------------------------- | ----------------------- | | 要素 i を追加 | mask | = (1 << i) | i番目のビットを1にする | | 要素 i を削除 | mask &= ~(1 << i) | i番目のビットを0にする | | 要素 i を持っているか確認 | mask & (1 << i) | i番目のビットが1かチェック | | 集合Aと集合Bを合体 | A | B | どちらかにある要素を1に | | 集合Aと集合Bの共通部分 | A & B | 両方にある要素を1に |

• N種類の品物（N ≤ 10）
• 各クーポンはどの品物を買えるかを表す 0/1 配列（長さN）

例：

N = 4
クーポン = [1, 0, 1, 0] → 品物1と3が無料

→ ビットマスク： 0101（2進）= 5（10進）

• 初期状態：何も持っていない → 0000
• クーポン[1,3] を使う → 0000 | 0101 = 0101
• 次にクーポン[2,4] → 0101 | 1010 = 1111

→ 1111 になれば全ての品物が揃った！

• N種類すべて揃った状態は、ビット列で 111...1（長さN）
• これは数値で言うと 2^N - 1

const goal = (1 << N) - 1;
if (current_mask === goal) {
    console.log('すべての品物が揃った！');
}

for (let mask = 0; mask < 1 << N; mask++) {
    // mask は 0〜2^N-1 の整数で、各ビットが品物の有無を表す
    for (let i = 0; i < N; i++) {
        if (mask & (1 << i)) {
            console.log(`品物${i + 1}が含まれている`);
        }
    }
}

| 特徴 | 内容 | | ------------------- | ----------------------------------------------------------------- | -------------------------------- | | 状態を数値で扱える | 配列やオブジェクトを使わなくても高速・簡潔に集合を表現 | | 高速処理 | ビット演算（&, |, ^, <<, >>）は非常に高速 | | 全探索に強い | 部分集合を 2^N 通りで簡単に列挙できる（N ≤ 20くらいまで現実的） | | BFSやDPとの相性抜群 | 状態空間をビットで表せると探索が劇的に効率化される |

もちろん！
今回は問題にも関係がある「BFS（幅優先探索）」について、初心者でもわかりやすく解説します。

BFS：Breadth-First Search（幅優先探索） とは、

スタート地点から、近い順（浅い順）にすべての状態（ノード）を調べる探索手法です。

たとえば迷路で「スタートからゴールまでの最短経路を見つけたい」とき：

• 最初はスタート地点にいる
• まずは 1歩先 に行ける場所をすべて調べる
• 次に、2歩先、3歩先 … と 順に距離を広げながら調べる
• ゴールに一番早くたどり着いた時点で、それが「最短経路」

これが BFS の基本的なアイデアです！

1. スタート地点をキューに入れる
2. キューが空になるまで以下を繰り返す：
   • キューから現在の状態を取り出す
   • その状態から行ける すべての隣接状態 を調べる
   • まだ訪れていないなら、キューに追加する

// BFSで状態を探索する
const queue = [];
const visited = new Set();

queue.push(start);
visited.add(start);

while (queue.length > 0) {
    const current = queue.shift(); // FIFO（先に入れたものを先に出す）

    for (const neighbor of getNextStates(current)) {
        if (!visited.has(neighbor)) {
            visited.add(neighbor);
            queue.push(neighbor);
        }
    }
}

目的：最小何枚のクーポンでN種類すべての品物を集められるか？

このときの BFS の使い方：

• 「最小クーポン数」＝「最短ステップ数」
• BFSは「先にたどり着いた状態が最短」と保証できるため、初めてゴール状態に達した時点でそれが最小手数

function bfs(start, goal) {
    const queue = [];
    const visited = new Set();

    queue.push({ state: start, steps: 0 });
    visited.add(start);

    while (queue.length > 0) {
        const { state, steps } = queue.shift();

        if (state === goal) return steps;

        for (const next of getNextStates(state)) {
            if (!visited.has(next)) {
                visited.add(next);
                queue.push({ state: next, steps: steps + 1 });
            }
        }
    }

    return -1; // 到達不能
}