正直者と不親切な人、計N人の証言が入力される。この内正直者は最大で何人存在し得るか、という問題。
12月からPython慣れのためにAtCoderやり始めて最新の方からぼちぼち過去問を触っているのだけど入力見て頭がフットーしそうになった
（ノートに文や図を雑書きしながら問題を読み込むのは大事ですね）。
解法
正直者は「1」、不親切な人は「0」で表すので、状態をNbit持つ事にして、全ての通りについて検証していけばいいです。
bit全探索ってやつですね。
N=3ならbitを000から111まで順に回していきます。
「001」なら1人目の証言について検証、「010」なら2人目の証言について検証、「011」なら1人目と2人目の証言について検証する....といった具合。
（何を血迷ったか「今001で1人目が2人目を正直としてるからこの時2人目の証言についても検証しないといけなくてそうなると2人目の証言によってn人目の証言も....ぐああ！」ってなってました。bit全探索の意味が無い....
その時点でbitが立ってる人の証言と各人の状態が正しいかどうかだけを確かめればいいですね）
解答
import sys
def kensho(x,tlist):
for lis in tlist:
if((x>>(lis[1]-1)) & 1 == lis[2]):
pass
else:
return -1
return bin(x).count('1')
def main():
N = int(input())
xy=[]
ans=0
for i in range(1,N+1):
An= int(input())
for j in range(0,An):
x, y = map(int, input().split())
xy.append([i,x,y])
cnt = N
tlist=[]
for x in range (2 ** cnt):
for y in range(cnt):
if((x>>y) & 1):
for z in xy:
if(z[0]==y+1):
tlist.append(z)
anstack = kensho(x,tlist)
if(ans<anstack):
ans=anstack
del tlist[:]
print(ans)
main()
相当冗長なクソコードになっている感じは否めないですがとりあえずACしたコード。
C問さえ理解するのに1～2時間掛かってしまっている・。・
解けた時の解放感は良いんですけど実際のコンテストではささっと解ける段階に至れていないのでまだまだ努力が必要ですね
v・。・v