Pythonで毎日AtCoder #47 - Qiita

はじめに 前回 #47 問題 考えたこと 制約を見ると$N,M$が10以下と小さいので力ずくで解けると思い、実装しました。スイッチがon/offの二択なのでbit全探索します。計算量は$O(2^N)$になりますが、$N$が小さいのでTLEしません。要素がそれぞれのスイッチのon/offの状態を表したboolのlistを作り、それぞれの状態での電球の点灯状況を確認します。 n, m = map(int,input().split()) ks = [list(map(int,input().split())) for _ in range(m)] p = list(map(int,input().split())) ans = 0 for i in range(2 ** n): on = [False] * n for j in range(n): #bit全探索 if ((i>>j) & 1