ABC147 C --HonestOrUnkind2 [Python]

・ ABC147 C --HonestOrUnkind2

The testimony of a total of N people, honest and unfriendly, is entered. The question is how many honest people can exist at the maximum. I started doing AtCoder to get used to Python from December, and I've been touching past questions from the latest ones, but when I saw the input, my head seemed to be sick. (It is important to read the problem while writing sentences and figures in the notebook).

solution

Honesty is represented by "1" and unfriendly person is represented by "0", so it is good to have Nbit state and verify all streets. It's a bit full search.

If N = 3, bit is rotated from 000 to 111 in order. "001" verifies the testimony of the first person, "010" verifies the testimony of the second person, "011" verifies the testimony of the first and second person, and so on. (What did you get lost in? "Now in 001, the first person is honest with the second person, so at this time we have to verify the testimony of the second person, and then the testimony of the second person will also be the testimony of the nth person .... Gua! There is no point in searching all bits ... You only have to check the testimony of the person who has the bit at that point and whether each person's condition is correct.)

answer

    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()

I can't deny the feeling that it's a fairly redundant fucking code, but for the time being, it's an AC code. It took an hour or two to understand even question C. ・ The feeling of liberation when it is solved is good, but in the actual contest, it has not reached the stage where it can be solved quickly, so it is still necessary to make efforts. v ・. ・ V