ABC187 C - 1-SAT から学んだ

5428 ワード
AtCoder Python AtCoderBeginnerContest Python テキストリンク

んー、何とかなりそうかも。

サクッと書いたが見事に TLE

SAT_rev1.py
from sys import exit
n = int(input())
lis = []
_lis = []

for _ in range(n):
    s = input()
    if s[0] == "!":
        _lis.append(s)
    else:
        lis.append(s)

for x in lis:        # len(lis) = 10**5
    if "!"+x in _lis:# len(_lis) = 10**5 の場合、10**10 となり TLE
        print(x)
        exit()
print("satisfiable")

※リスト x in s の計算量 O(n) を参照

じゃあ、試しに辞書にしてみよう。
以下で通った。

SAT_rev2.py
from sys import exit
n = int(input())
lis = []
dic = {}

for _ in range(n):
    s = input()
    if s[0] == "!":
        if s not in dic:
            dic[s] = 0
        dic[s] += 1
    else:
        lis.append(s)

for x in lis:       #計算量 O(N)
    if "!"+x in dic:#計算量 O(1) 
        print(x)
        exit()
print("satisfiable")

神曰く、辞書、set は in演算子は O(1) で済む。
勉強になった。