AtCoder Beginner Contest (ABC) 187 PythonでC問題解いてみた
前回解いたやつ
こんにちは。メリーです。
最近は友達とAmong Usをやったりしてます。
人数が6-7人くらいの少人数だし、身内なのでインポスターのサボタージュの鳴らし方加減で誰がインポスターなのか察してしまうという・・・。
YoutubeでもAmong Us の実況とか見ると最近はMODの動画が多いのでやってみたいなーって話もしてたり。
MOD作るの楽しそうなのでいつかやってみたいなー
そんなこんなで本日もAtCoder Beginner Contest (abc) 187 C問題解いていきます。
今日のやつはだいぶ詰まりました。
何回やってもTLEになる・・・。
言語はPython、提出はPyPyです。
目次
C問題 挑戦編
問題文
文字列が不満な文字列かどうかを判別するプログラムを書いてくださいという問題。
不満な文字列とはなんやねん
※不満な文字列とは「!」を1個か0個足すことで、他の文字列と被る文字列ですね。
うーん、まぁそんな難しい問題じゃないっぽいから、そのまんまやればいけるやろーって気分でそのままやりました。
それがこんな感じ。
n = int(input())
s = [input() for _ in range(n)]
flg = 0
for i in range(len(s)):
if s[i][0] == '!':
continue
else:
s1 = "!" + s[i]
if s1 in s:
ans = s[i]
flg = 1
break
if flg:
print(ans)
else:
print("satisfiable")
問題文的に、文字列Tに該当するのは文字列Sの中に存在する。
また、「!」の付いていない文字列が文字列Tに該当しそうなので、「!」がついている場合のみ省いて全探索しました。
結果は！！
TLEでした。
このコードだと、12個のサンプルがTLEになりました。
計算量を工夫するためにいじったコードがこれです。
n = int(input())
s = []
s0 = []
for i in range(n):
S = input()
if S[0] == '!':
s0.append(S)
else:
s.append(S)
flg = 0
if len(s) > len(s0):
for i in range(len(s0)):
t = s0[i][1:]
if t in s:
flg = 1
break
else:
for i in range(len(s)):
t = s[i]
if "!" + t in s0:
flg = 1
break
if flg:
print(t)
else:
print("satisfiable")
工夫したのはこの点
- inputで「!」が付いているのかついていないのかグループ分け
- 「!」が付いているほうとついていないほうで、数が少ない方を全探索
- 「!」が付いている場合(s0)は、「!」を取り除きそれがもう一つのグループ(s)にあるかどうかチェック
- 「!」が付いていない場合(s)は、「!」を付けてそれがもう一つのグループ(s0)にあるかをチェック
これで計算量を半分に抑えられるはず！！と思い再提出。
TLEでした。
このコードでは、6個のサンプルがTLEになりました。
さっきのコードよりTLE少なくなったね。やったね。
TLEになってる時点でそれは
C問題 解決編
というわけで解決編を。
TLEから詰まって解けなかったので、解説見ました。
今回の問題点は
- listを使用した時のinの速度
でした。
実は、Pythonでのlistでinを行うと、計算量がO(N)になるみたいです。
一方、setでinを行うと、計算量がO(1)でできます。
というのは、listでinを行うと、listの0番目の要素から順番に一致するかどうかを確認するっぽいので、計算量がO(N)になるみたいです。
一方、setでは、ハッシュテーブルで実装されているため、確認する時間が非常に高速らしいです。
ハッシュテーブルでは、各要素に添え字のようなものが付いていて、その添え字のようなものは、ハッシュ関数という計算方法で計算できます。
この場合、aが要素内にあるかを確認したいときは、aをハッシュ関数で計算した値があるかないかを調べるため、非常に高速で計算できるみたいです。
このような違いがあるため、速度に差がでるようです。
というわけでACしたコードを
n = int(input())
s = set()
for i in range(n):
S = input()
s.add(S)
flg = 0
for ans in s:
if "!" + ans in s:
flg = 1
t = ans
break
if flg:
print(t)
else:
print("satisfiable")
はい、setに要素を追加していって、あとは問題文に忠実にやるだけですね。
この問題では、setが使えるかどうかが命運を分けるものでしたね。
ではまた後日。
