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

Recommended Posts

ABC147 C --HonestOrUnkind2 [Python]
ABC163 C problem with python3
ABC memorandum [ABC163 C --managementr] (Python)
ABC188 C problem with python3
ABC187 C problem with python
ABC memorandum [ABC159 C --Maximum Volume] (Python)
Solve ABC163 A ~ C with Python
ABC127 A, B, C Explanation (python)
ABC166 in Python A ~ C problem
Solve ABC168 A ~ C with Python
ABC memorandum [ABC161 C --Replacing Integer] (Python)
Solve ABC036 A ~ C in Python
Solved AtCoder ABC 114 C-755 with Python3
Solve ABC162 A ~ C with Python
Solve ABC167 A ~ C with Python
ABC128 A, B, C commentary (python)
ABC126 A, B, C Explanation (python)
Solve ABC037 A ~ C in Python
Beginner ABC154 (Python)
AtCoder ABC 174 Python
Beginner ABC155 (Python)
python C ++ notes
python, openFrameworks (c ++)
Beginner ABC157 (Python)
AtCoder ABC 175 Python
Solve ABC175 A, B, C in Python
Python C / C ++ Extension Pattern-Pointer
ABC memorandum [ABC160 C --Traveling Salesman around Lake] (Python)
Next Python in C
Solve ABC169 in Python
C API in Python 3
Challenge AtCoder (ABC) 164 with Python! A ~ C problem
Extend python in C ++ (Boost.NumPy)
AtCoder ABC 177 Python (A ~ E)
Solve AtCoder ABC166 with python
Python, Java, C ++ speed comparison
PyTorch C ++ VS Python (2019 Edition)
AtCoder ABC 178 Python (A ~ E)
Atcoder ABC164 A-C in Python
C / C ++ programmer challenges Python (class)
ABC129 A, B, C commentary
Solve ABC176 E in Python
Atcoder ABC167 A-D in Python
Binary search in Python / C ++
Solve ABC175 D in Python
Atcoder ABC165 A-D in Python
Multi-stage selection (C # / Python) (old)
I tried Python C extension
Python started by C programmers
Atcoder ABC166 A-E in Python
AtCoder ABC 182 Python (A ~ D)
Solve AtCoder ABC 186 with Python
Atcoder ABC169 A-E in Python
AtCoder ABC177 A-D in python
[AtCoder explanation] Control ABC180 A, B, C problems with Python!
[AtCoder explanation] Control ABC188 A, B, C problems with Python!
[AtCoder explanation] Control ABC158 A, B, C problems with Python!
AtCoder ABC151 Problem D Speed comparison in C ++ / Python / PyPy
[AtCoder explanation] Control ABC164 A, B, C problems with Python!
[AtCoder explanation] Control ABC168 A, B, C problems with Python!
ABC168