競プロ初中級者100問

ABC128C Switches

この記事で使うアルゴリズム

全探索

はじめに

カテゴリー競プロ初中級者100問では、Qiitaにて@e869120さんがレッドコーダーが教える、競プロ・AtCoder上達のガイドライン【中級編：目指せ水色コーダー！】としてまとめられている100問をPythonで解いています。

全問題の一覧はこちらです

問題

https://atcoder.jp/contests/abc128/tasks/abc128_c

この問題は全探索を用いて解くことができます。

方針

Nの最大値は10なので、計算量がO(kM2^N)であるビット全探索でも十分間に合います。

コード

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
from itertools import product
N, M = map(int,input().split())
S = []
for m in range(M):
    s = list(map(int,input().split()))
    S.append(s[1:])
P = list(map(int,input().split()))

ans = 0
for c in product([0,1],repeat=N):
    ok = True
    for m in range(M):
        sm = 0
        for s in S[m]:
            sm += c[s-1]
        if sm % 2 != P[m]:
            ok = False
            break
    if ok:
        ans += 1
print (ans)

記事情報

  • 投稿日：2020年5月13日
  • 最終更新日：2020年5月13日