🛰️
# ABC187 C - 1-SAT
ABC187 C - 1-SAT
問題へのリンク
問題概要
! を0文字か1文字付加したものである。
文字列 ! を0文字付加しても1文字付加しても
制約
ABC中の解答
問題のタイトルの SAT とは充足可能性問題 (satisfiability problem, SAT)のことのようだ。
制約が TLE になる。比較を早くするためリストではなくセット
-
S_i !がないなら!を先頭に足したものとG -
S_i !があるなら!を抜いたものとG S_i
とした。
N = int(input())
G = set([])
for _ in range(N):
s = input()
if ('!' + s) in G:
print(s)
exit()
if s[0] == '!' and len(s) >= 2 and s[1:] in G:
print(s[1:])
exit()
G.add(s)
print('satisfiable')
公式解法1
ABC中の解答では順次文字が追加される度に処理をしていったが、全部の文字列を比較しするとか１つ目の箇条書きだけ考えたらよいとわかる。(!がある方からは見つけられないが、!がない方からは見つけられるので)
したがって、以下のようにシンプルに実装できる。冷静に考えるのが大事だとわかる問題だ。
N = int(input())
S = set(input() for _ in range(N))
for s in S:
if ('!' + s) in S:
print(s)
exit()
print('satisfiable')
ちなみにセットをリストにするとちゃんと(?)計算コストが高くなり TLE となる。
N = int(input())
S = set(input() for _ in range(N))
for s in S:
if ('!' + s) in S:
print(s)
exit()
print('satisfiable')
Discussion
$N$個の文字列$S_1, \dots, .., S_N$がある。のようにLaTeXつけると読みやすいかなと思いました！
公式解法１がきれいで勉強になりました＞＜
ありがとうございます。対応してみました！