Help us understand the problem. What is going on with this article?

ABC147 C - HonestOrUnkind2[Python]

ABC147 C - HonestOrUnkind2

正直者と不親切な人、計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

yunozi
Pythonはじめました AtCoderはじめました しゃかいじんです
Why not register and get more from Qiita?
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away
Comments
No comments
Sign up for free and join this conversation.
If you already have a Qiita account
Why do not you register as a user and use Qiita more conveniently?
You need to log in to use this function. Qiita can be used more conveniently after logging in.
You seem to be reading articles frequently this month. Qiita can be used more conveniently after logging in.
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away
ユーザーは見つかりませんでした