倉庫の電灯を全部点けるスイッチ

全探索
問題 11
ふつう
目安 31 分

押すたびに決まった電灯の点灯と消灯を入れ替えるスイッチが並ぶ。押す順番は結果に関係ないことに気づき、押すか押さないかの全通りをビットで調べて、最も少ない押す回数を答える練習です。

本番の試験は PC で受けることが多いので、PC での練習をすすめます。スマホでも、読んで、書いて、採点するところまで動きます。

入力は標準入力から読み、答えは標準出力に書きます。1 テストあたり 2 秒までです。

問題

倉庫に 1 から M までの番号の付いた M 個の電灯と、1 から N までの番号の付いた N 個のスイッチがあります。スイッチ i を 1 回押すと、決まった k_i 個の電灯のそれぞれについて、点いていれば消え、消えていれば点きます。ほかの電灯は変わりません。

いまの電灯の状態が与えられます。スイッチを何回か押して、M 個の電灯を全部点いた状態にしたいです。同じスイッチを何回押してもかまいません。全部を点けるのに必要な、スイッチを押す回数の合計の最小を出力してください。最初から全部点いていれば 0 です。どう押しても全部を点けられないときは -1 を出力してください。

入力の形式

N M
S
k_1 c_1,1 c_1,2 ... c_1,k_1
k_2 c_2,1 c_2,2 ... c_2,k_2
...
k_N c_N,1 c_N,2 ... c_N,k_N

1 行目にスイッチの数 N と電灯の数 M が並びます。2 行目の S は 0 と 1 だけの M 文字の文字列で、左から j 文字目が 1 なら電灯 j はいま点いていて、0 なら消えています。3 行目から N 行は、i 行目がスイッチ i の説明です。先頭の k_i が入れ替える電灯の数で、続く k_i 個がその電灯の番号です。

出力の形式

押す回数の合計の最小 (全部を点けられないときは -1) を 1 行に出力します。

制約

N は 1 以上 16 以下です
M は 1 以上 20 以下です
S は 0 と 1 だけからなる長さ M の文字列です
k_i は 1 以上 M 以下です
電灯の番号 c_i,1 から c_i,k_i は 1 以上 M 以下で、小さい順に並び、同じ番号はありません

入力と出力の例

例 1

電灯 1 と 3 が点いていて、2 と 4 が消えています。スイッチ 1 (電灯 1 と 2) とスイッチ 2 (電灯 1 と 4) を 1 回ずつ押すと、電灯 1 は 2 回入れ替わって点いたまま、2 と 4 が点き、全部が点きます。1 回だけで全部を点けるスイッチは無いので、答えは 2 です。

入力

出力

例 2

スイッチ 1 もスイッチ 2 も電灯 1 と 2 をいっしょに入れ替えるので、電灯 1 だけ消えた状態から、電灯 1 だけを点けることはできません。

入力

出力

-1

例 3

最初から全部点いているときは、押さなくてよいので 0 です。

入力

1 3
111
1 2

出力

ヒント

まだ開いていません

付箋は 3 枚。下の段ほど答えに近づきます

ヒント 2
ヒント 3答えに近い

全部のテストに通ると、解答と考え方が開きます。

先にヒントを試すと、自分で解けた手応えが残ります。どうしても詰まったときは、ここから開けます。

解答

電灯の状態を整数のビットで持ちます。スイッチ i も、入れ替える電灯のビットを立てた整数 masks[i] にしておきます。押し方 b を 0 から 2 の N 乗 - 1 まで全部試し、b で押すスイッチの masks を、いまの状態に排他的論理和で重ねます。結果が全部 1 (2 の M 乗 - 1) になった押し方のうち、押したスイッチの数 (b の 1 の桁の数) がいちばん少ないものが答えです。

Python

import sys

data = sys.stdin.read().split()
n, m = int(data[0]), int(data[1])
start = 0
for j, ch in enumerate(data[2]):
    if ch == "1":
        start |= 1 << j
masks = []
pos = 3
for i in range(n):
    k = int(data[pos])
    mask = 0
    for c in data[pos + 1:pos + 1 + k]:
        mask |= 1 << (int(c) - 1)
    masks.append(mask)
    pos += 1 + k

full = (1 << m) - 1
best = -1
for pressed in range(1 << n):
    state = start
    for i in range(n):
        if pressed >> i & 1:
            state ^= masks[i]
    if state == full:
        count = bin(pressed).count("1")
        if best == -1 or count < best:
            best = count

print(best)

JavaScript

const data = require("fs").readFileSync(0, "utf8").split(/\s+/).filter(Boolean);
const n = Number(data[0]);
const m = Number(data[1]);
let start = 0;
for (let j = 0; j < m; j++) {
  if (data[2][j] === "1") start |= 1 << j;
}
const masks = [];
let pos = 3;
for (let i = 0; i < n; i++) {
  const k = Number(data[pos]);
  let mask = 0;
  for (let t = 1; t <= k; t++) mask |= 1 << (Number(data[pos + t]) - 1);
  masks.push(mask);
  pos += 1 + k;
}

const full = (1 << m) - 1;
let best = -1;
for (let pressed = 0; pressed < 1 << n; pressed++) {
  let state = start;
  let count = 0;
  for (let i = 0; i < n; i++) {
    if ((pressed >> i) & 1) {
      state ^= masks[i];
      count++;
    }
  }
  if (state === full && (best === -1 || count < best)) best = count;
}

console.log(best);

計算量

時間は O(2^N × N) です。N が 16 なら 6 万 5536 通りに 16 回ずつで、100 万回ほどの計算です。押す順番まで区別して、まだ押していないスイッチを 1 つずつ選んで押していく書き方 (順番を全部試す書き方) は、調べる並びの数が N の階乗ほどになり、N が 16 では 20 兆通りを越えて時間切れになります。小さい N では同じ答えが出るので、入力が小さいうちは誤りに気づきにくい書き方です。

よくある間違い

押す順番まで全部試してしまう。入れ替えは順番によらないので、押すか押さないかの組だけで足ります
同じスイッチを 2 回以上押す場合まで数えようとして、終わらない探索を書く。2 回押すのは押さないのと同じです
電灯の番号は 1 から、ビットの桁は 0 から数えることを忘れて、1 つずれる。電灯 j は 1 << (j - 1) です
最初から全部点いているときに 0 ではなく -1 を出す。押し方 b = 0 (何も押さない) も試す範囲に入れます

解答を動かした版 Python 3.12.14Node.js 22.23.4確認日 2026/10/31

import sys data = sys.stdin.read().split() n, m = int(data[0]), int(data[1]) state = data[2] switches = [] pos = 3 for i in range(n): k = int(data[pos]) switches.append([int(c) for c in data[pos + 1:pos + 1 + k]]) pos += 1 + k # ここから書く