ABC187 C問題 1-SAT を集合を使って解く
ABC187 C問題 1-SAT を集合(PythonのSet)を使って解いた解説です。
N 個の文字列
S1,S2,…,SN が与えられます。 各文字列は、英小文字からなる空でない文字列の先頭に ! を 0 文字か 1 文字付加したものです。
文字列 T は、T の先頭に ! を 0 文字付加しても 1 文字付加しても S1,S2,…,SN のいずれかに一致するとき、不満な文字列であるといいます。
不満な文字列があるかどうか判定し、あれば 1 つ示してください。
問題文をざっくりと解釈すると、'!'マークが先頭についた文字列の集合とついていない文字列の集合があって、
その集合の積集合に何かしら存在したらそれを出力。
その積集合に何も存在しなければ'satisfiable'と出力します。
本当は積集合を作る必要もなく、setの中を探索するときの計算量はO(1)なので、
'!'マークがついていたら、ついていない文字列に変更して、setの中でその文字列が含まれていればすぐに出力して終了です。
周りくどい解き方ですけど、積集合をとるやり方は以下の通りです。
N = int(input()) b_set = set() n_set = set() for _ in range(N): s = input() if s[0] == '!': s_s = s[1:] b_set.add(s_s) continue n_set.add(s) both = b_set & n_set if len(both): print(both.pop()) exit() print('satisfiable')