【AtCoder】PythonでABC187のC問題を解説

この記事では2021年1月2日に行われたAtCoder Beginner Contest 187のC問題について、Python3における解法をお伝えします。

なるべく分かりやすく解説できるよう心がけますが、競プロ初心者のため改善点・問題点がありましたらコメントまたはTwitterでご指摘ください。

Twitter：@soh_1121_

C：1-SAT

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

制約
　・1 ≦ N ≦ 2 ✕ 10⁵
　・1 ≦ |S_i | ≦ 10
　・S_i は英小文字からなる空でない文字列の先頭に ! を0文字か1文字付加したものである。

入力
入力は以下の形式で標準入力から与えられる。
N
S1
︙
SN

出力
不満な文字列が存在する場合、不満な文字列を1つ出力せよ。
不満な文字列が存在しない場合、satisfiableと出力せよ。

AtCoder Beginner Contest 187 C – 1-SAT

非常にややこしく問題文が書かれているように思えますが、要約するとN 個の文字列 S₁, S₂ , … , S_N から1個ずつ取り出して頭に ! を付けた際に、同じものがN 個の文字列 S₁, S₂ , … , S_N に存在するかどうかという問題。

「文字列T がなんでもいいならsatisfiableはありえないしな…」など、問題文の理解にだいぶ時間を使いました…

def main():
    N = int(input())
    S = set(input() for _ in range(N))
    for s in S:
      if "!" + s in S:
        print(s)
        return
    print("satisfiable")


main()

N 個の文字列 S₁, S₂ , … , S_N をsetで受け取るのがポイントで、これがlistだとTLE（タイムアウト）が発生します。 in を使う際にはlistでは全探索を行います。一方でsetはハッシュテーブルなので、調べたい要素からハッシュ値を求め、ハッシュ値を元に調べたい要素が含まれているか調べます。これによりlistでO(n)で実現していた探索をsetではO(1)で行えるとのことです。

S を1個ずつ取り出して、”!”を付けてS すべてと比較して一致するものがあれば該当するS を出力、N 個の文字列いずれも不一致であればsatisfiableを出力してACです。

まとめ：listを使うか、setを使うか見極めよう

この記事では2021年1月2日に行われたAtCoder Beginner Contest 187のC問題について、Python3における解法をお伝えしました。

listを使うか、setを使うか、慣れないうちは悩むと思いますが、自分は基本的に「順番を保持する必要がある、または重複するものがある場合はlist」で「それ以外はset」とすることが多いです。

今回の解説記事を書くことでsetがハッシュテーブルだから早いということがわかり、自分としても勉強になりました。

このような解説記事を通じて、さらに精進していければと思います。