bit全探索

bit_search.py

##
## ABC079C Train Ticket
##

n = input()
op_cnt = len(n) - 1 #隙間の数
for i in range(2**op_cnt): #+ or -で2通りずつ存在する（全探索）
    op = ["-"]*op_cnt
    for j in range(op_cnt): #opそれぞれビットシフト
        if ((i >> j)&1): #iの全探索分それぞれで、j bitシフトしてj番目が1かどうか
            op[(op_cnt - 1)-j] = "+" #例えば４つ隙間があったら、３ビットシフトで最初の隙間でop[0]にプラスを入れる
    #ここで計算の隙間が決まる
    formula = ""
    for p_n, p_o in zip(n,op+[""]):
        #zipで２つの行列を同時に回す
        #A+-B+-C+-Dのように繋げる。隙間は１こ少ないので""
        formula += (p_n + p_o)
    #計算式が完成（文字列）
    if eval(formula)==7: #eval()は文字列で計算する
        print(formula + "=7")
        break #必ず解があるから

##
## ABC128C Switches
##

n,m = map(int,input().split())
list_k = []

for i in range(m):
    list_k.append(list(map(int,input().split())))
p = list(map(int,input().split()))

#confirmation of input
#print(list_k)
#print(p)

ans = 0
for i in range(2**n):
    switch = [0]*n
    for j in range(n):
        if ((i>>j)&1):
            switch[n-1-j] += 1
    #ここまででスイッチが１通り決まる
    lamp = [0]*m
    #ここからm個の電球を調べていく
    for k in range(m):
        on_num = 0
        for l in range(1,list_k[k][0]+1):#switch number
            if switch[list_k[k][l]-1] == 1:#switchがonかどうか
                on_num += 1  
        #mの電球がついているか        
        if on_num%2 == p[k]:
            lamp[k] += 1
    #print(lamp)        
    if sum(lamp) == m:
        ans += 1
print(ans)

##
## ABC167C Skill Up
##
n,m,x = map(int,input().split())
list_c = []

for i in range(n):
    list_c.append(list(map(int,input().split())))

#check
#print(list_c)

# read book = 1 
min_cost = float("inf")
for i in range(2**n): #本を読む読まないの組み合わせ
    book = [0]*n
    cost = 0
    understanding = [0]*m
    for j in range(n):
        if (i>>j&1):
            book[n-1-j] = 1
            cost += list_c[n-1-j][0]
            understanding = [x+y for (x,y) in zip(understanding,list_c[n-1-j][1:])]
        #ここで本を読むか読まないか、コスト、理解度が決まる
    #今の本のセットでクリアしているか判定
    if min(understanding) >= x:
        min_cost = min(min_cost,cost)
if min_cost == float("inf"):
    print(-1)
else:
    print(min_cost)

##
## ABC197 C ORXOR (PyPyでないと間に合わないです)
##
n = int(input())
a = list(map(int,input().split()))
ans = []
for i in range(2**(n-1)):
    separation = [0]*(n-1)
    for j in range(n-1):
        if (i>>j&1):
            separation[(n-1)-1-j] = 1
        #ここまでで区切りを入れるかどうかのリストが完成   
    #print(separation)
    ored = 0  # x | 0 = xだから
    xored = 0 # x ^ 0 = xだから
    #区切りがくるまでorを計算し、区切りが来たらxorを計算しorを0に戻す
    for idx,k in enumerate(separation):
        ored |= a[idx]
        #print(ored)
        if separation[idx]&1:
            xored ^= ored
            ored = 0
    #separationより１つ長い最後を計算
    ored |= a[n-1]
    xored ^= ored
    ans.append(xored)
print(min(ans))