AtCoder-ABC187 C - 1-SAT【Python解答例】

AtCoder Beginner Contest187に出場した際のC問題の解答例を書いていきます。
AtCoder Beginner Contest 187 - AtCoder

AtCoder Beginner Contest187 C - 1-SAT

C - 1-SAT

問題文

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

制約

・1≤N≤2×10^5
・1≤|Si|≤10
・Siは英小文字からなる空でない文字列の先頭に ! を0文字か1文字付加したものである。

解答例

n = int(input())

S = []
for i in range(n):
    array = input()
    S.append(array)

S_set = set(S)

for i in range(n):
    if S[i][0] != "!":
        continue
    else :
        if S[i][1:] in S_set:
            print(S[i][1:])
            break
else:
    print("satisfiable")

解説

N個の文字列が与えられ、先頭が！でない文字列と先頭が！の文字列があるか、あればその文字列を出力するという問題です。

ループで与えられたN個の文字列を確認していきました。
ループでは先頭が！の文字列を探しています。
先頭が！であれば、！を抜いた文字列がN個の文字列の中にあるかを探します。
もし、！を抜いた文字列があれば、それが解答になります。
一致する文字列がないままループを抜ければ、satisfiableを出力すればACでした。

最初、！を抜いた文字列を探すときにin演算子を使いましたがそのときは制限時間を超えてしまいました。
コンテスト中に検索したらsetを使うと早く検索できることを知り、プログラムを変更しました。
まったく理由が理解できていませんが、setをつかえばACでした。

この違いも学習しないといけないです…

理解は追いついてないですがなんとかC問題まで解けました。
今後のコンテストはC問題までノルマにできるよう頑張ります。

ABC187の記事はD問題まで解いて記事にしていきたいと思います。

ABC187の関連記事はこちら
ebisuke33.hatenablog.com
ebisuke33.hatenablog.com