【pythonでABC187を解説】C - 1-SAT

問題概要

問題ページ

問題文

$N$ 個の文字列 $S_1, S_2, \dots, S_N$ が与えられます。
各文字列は、英小文字からなる空でない文字列の先頭に ! を $0$ 文字か $1$ 文字付加したものです。
文字列 $T$ は、$T$ の先頭に ! を $0$ 文字付加しても $1$ 文字付加しても $S_1, S_2, \dots, S_N$ のいずれかに一致するとき、不満な文字列であるといいます。
不満な文字列があるかどうか判定し、あれば $1$ つ示してください。

制約

• $1 \le N \le 2 \times 10^5$
• $1 \le |S_i| \le 10$
• $S_i$ は英小文字からなる空でない文字列の先頭に ! を $0$ 文字か $1$ 文字付加したものである。

問題の考察

例えば文字列「!AtCoder」「AtCoder」があれば「AtCoder」が不満な文字列となる。

存在チェックをする時はcollection.defaultdict()を使うのが一般的でこの問題でも同じである。

不満な文字列が存在する場合は、例えば「!AtCoder」「AtCoder」のいずれも存在するので「!AtCoder」側から存在チェックをすれば問題ない。

たびすけ

存在チェックの際にcollection.defaultdict()を使えるようにしましょう！
listは計算量$O(N)$で、辞書型は$O(log N)$です。

ACコード

import sys
import collections


def solve():
    input = sys.stdin.readline
    mod = 10 ** 9 + 7
    n = int(input().rstrip('\n'))
    d = collections.defaultdict(int)
    for i in range(n):
        s = str(input().rstrip('\n'))
        d[s]
    for k in d.keys():
        if k[0] == "!":
            if k[1:] in d:
                print(k[1:])
                exit()
    print("satisfiable")


if __name__ == '__main__':
    solve()