過去問精選100 問 全探索：bit全探索【Python解答例】

こちらの記事で紹介されている初中級者が解くべき過去問精選100 問を続けて解いていきます。
レッドコーダーが教える、競プロ・AtCoder上達のガイドライン【中級編：目指せ水色コーダー！】 - Qiita

この記事は全探索：bit全探索編です。
bit全探索を初めて学習しました。
基本的な部分は理解したつもりなので頑張って解いていきます。

ALDS_5_A - 総当たり

ALDS_5_A

問題文

長さ n の数列 A と整数 m に対して、A の要素の中のいくつかの要素を足しあわせて m が作れるかどうかを判定するプログラムを作成してください。A の各要素は１度だけ使うことができます。
数列 A が与えられたうえで、質問として q 個の mi が与えれるので、それぞれについて "yes" または "no" と出力してください。

解答例

n = int(input().strip())
a = list(map(int,input().split()))
q = int(input().strip())
m = list(map(int,input().split()))

sum_alist = []
for i in range(2 ** n): # (※1)
    sum_a = 0
    for j in range(n):
       if (i >> j) & 1: # (※2)
            sum_a += a[j]
    sum_alist.append(sum_a)

for i in range(q):
    if m[i] in sum_alist:
        print("yes")
    else:
        print("no")

解説

数列Aから作れる数字をbit全探索を用いてsum_alistに格納していきます。

(※1)で0～2^nの数字(例として5)を作成します。
(※2)では(※1)で作成した数字（例として5）の2進数を（5の2進数 = 101）を右シフトしています。
j = 0 のとき…101はシフトしない。101の一番右が1なのでifの条件はTrueとなり、sum_aにa[0]を足す。
j = 1 のとき…101は1回右シフトし10となる。10の一番右が0なのでifの条件はFalseとなる。
j = 2 のとき…101は2回右シフトし1となる。1の一番右が1なのでifの条件はTrueとなり、sum_aにa[2]を足す。
上記を繰り返すと数列Aの要素のすべての足しあわせかたを試すことができ、その数値はsum_alistに格納されます。

あとはmがsum_alistに含まれているか （初めて使いましたが）in を用いて確認し、結果を出力すればOKでした。

ABC128 C - Switches

C - Switches

問題文

on と off の状態を持つN個の スイッチとM個の電球があります。スイッチには1からNの、電球には1からMの番号がついています。
電球iはki個のスイッチに繋がっており、スイッチsi1,si2,...,sikiのうち on になっているスイッチの個数を2で割った余りがpiに等しい時に点灯します。
全ての電球が点灯するようなスイッチの on/off の状態の組み合わせは何通りあるでしょうか。

制約

・1≤N,M≤10
・1≤ki≤N
・1≤sij≤N
・sia≠sib(a≠b)
・piは0または 1
・入力は全て整数である

解答例

n, m = map(int,input().strip().split())
s_list = []
for i in range(m):
    array = list(map(int,input().split()))
    array.pop(0)
    s_list.append(array)
p = list(map(int,input().strip().split()))

ans = 0

for i in range(2 ** n): # スイッチON/OFFパターン
    can = 1
    for j in range(m): # 各電球のループ
        num_on = 0
        for k in range(n): # 各スイッチのループ
            if i >> k & 1 and k + 1 in s_list[j]:
                num_on += 1
        if num_on % 2 != p[j]:
            can = 0
    if can == 1:
        ans += 1

print(ans)

解説

N個のスイッチとM個の電球があり、電球iにはki個のスイッチにつながっています。
ki個のスイッチのうちONになっている個数を2で割った余りがpiと一致すれば点灯し、すべての電球が点灯するスイッチON/OFFの組み合わせを求めます。

3重ループで電球がすべて点灯するか調べています。
まずはスイッチのON/OFFパターンのループです。
そのON/OFFパターンに対して電球jが点灯するか調べます。
電球jに対して、スイッチのループもまわします。
このとき、スイッチのON/OFFパターンからスイッチがONしているかif文で確認しています。
スイッチがONしており、電球mにつながっていたらnum_onを1増加させます。
スイッチのループが抜けたら2で割った余りをpと比較します。
もしpと異なっていたらすべての電球を点灯させることはできないのでcanフラグを0にします。
電球のループを抜けた後もcanフラグが1のままなら電球はすべて点灯していることになりますので、ans変数を1増加させます。

この3重ループを抜けたあとに出力すればACでした。

bit全探索編は正直難しくここまでしか理解できませんでした。
内容を理解出来たら順次追記していきます。

初中級者が解くべき過去問精選100 問の記事をまとめたページはこちら
ebisuke33.hatenablog.com

蟻本の類題も解いていますので興味があればこちらもおすすめです。
ebisuke33.hatenablog.com