40代文系社内SEがAtCoder Beginner Contest 128 C - Switchesを解いてみた

AtCoder Beginner Contest 128 C - Switches

まず問題文を読んでみる。

1行目と3行目は問題ないが、2行目がうまくのみこめない。

「電球iはki個のスイッチに繋がっており、スイッチsi1, si2, ..., sikiのうちonになっているスイッチの個数を2で割った余りがpiに等しいときに点灯します。」

ちょっとずつ分解してみる。

まず、piは制約に0または1と記載されているので、2で割った余りがpiに等しいとは、つまり偶数か奇数ということ。

「全部がonだったら」とか、「どれかひとつがonだったら」なら容易にイメージできるのに。

残りの前半部分については、電球ごとに繋がっているスイッチは異なり、

個数がkiで示され、続けてsijでどのスイッチに繋がっているかが示される。

続けて制約をみる。

NもMも10以下というのはかなり小さい値だ。

それ以外は特に気になることはなかった。

スイッチの状態がon/offの2種類であることと、個数が最大10個という制約から、スイッチの状態が全探索できそうだ。

$2^{10} = 1024$

電球が点灯しているかどうかを判定するには、電球ごとにonになっているスイッチを数えなければならない。

電球もスイッチも最大10個だから、最大でも10 * 10で網羅できる。

あとは実装方法だが、スイッチの状態がon/offの2種類なのでbit全探索が使える。

0以上(2^N)未満までループで回せば網羅できる。

例えば入力例1だと、0(00)、1(01)、2(10)、3(11)の4通りになる。

以上より、以下3ステップで問題を解く。

1. スイッチの状態ごとに、全ての電球が点灯しているか判定する

2. 電球ごとに、点灯しているか判定する

3. 電球に繋がっているスイッチごとに、onになっているか判定する

(let* ((n (read))
       (m (read))
       (k (make-array m))
       (s (make-array m :initial-element nil))
       (p (make-array m)))

  ;; k, sを読み込み
  (loop for i from 0 below m
        for ki = (read)
        do (setf (aref k i) ki)
           (loop repeat ki
                 for sij = (read)
                 do (push sij (aref s i))))

  ;; pを読み込み
  (loop for i from 0 below m
        for p-i = (read)
        do (setf (aref p i) p-i))

  ;; on/off
  (loop for stat from 0 below (expt 2 n)
        ;; 点灯している電球の個数
        for light-on = (loop for light from 0 below m
                             ;; onになっているスイッチの個数
                             for switch-on = (loop for switch in (aref s light)
                                                   count (logbitp (1- switch) stat))
                             count (= (mod switch-on 2)
                                      (aref p light)))
        count (= light-on m)
          into it
    finally
       (format t "~A~%" it)))