ABC解説

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

問題概要

問題ページ

C - 1-SAT
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()を使うのが一般的でこの問題でも同じである。

不満な文字列のチェック方法

  • collection.defaultdict()（以下辞書）に入力文字列を格納する
  • 辞書の各keyのうち先頭が!のものを存在確認
  • 先頭から!を取り除いた文字列が辞書に存在するか確認する
  • 存在していれば文字列を出力
  • 全てチェックして重複がなければsatisfiableを出力

不満な文字列が存在する場合は、例えば「!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()

-ABC解説
-