Atcoder Beginner Contest 164 振り返り(A-C) 【Python】

はじめに

AtCoder Beginner Contest 000の振り返りをします。
こんにちは、tmoriです。 2020年4月27日に行われたABC 164の振り返りをします。 今回はA問題からC問題を扱います。

atcoder.jp

A - Sheep and Wolves

SとWの数値比較の問題

提出したプログラム

# https://atcoder.jp/contests/abc164/submissions/12334638

a,b = map(int, input().split())
if b >= a:
    print("unsafe")
else:
    print("safe")

B - Battle

色々な回答方法があると思うんですけど、一番フローがわかりやすい方法で解きました。速度や効率はあまり良くないので、制約は十分に確認する必要があると思いますが、今回の場合は計算量的に行けそうだと判断しました。

提出したプログラム

# https://atcoder.jp/contests/abc164/submissions/12350857

a,b,c,d = map(int, input().split())

while True:
    c -= b
    if c <= 0:
        print("Yes")
        break
    a -= d
    if a <= 0:
        print("No")
        break

公式の解説の通り、それぞれの変数で割り算して、何回目に体力が0以下になるかを考えた方がスマートだと思います。

C - gacha

問題文を読んだとき、文字を取得するたびにリストから重複確認すれば行けそうだけどTLEになりそーと思いながら提出したら案の定TLE。

提出したプログラム

# TLEしたソースコード
# https://atcoder.jp/contests/abc164/submissions/12363327

N = int(input())
str_list = []

for i in range(N):
    n = input()
    if n in str_list:
        continue
    else:
        str_list.append(n)
print(len(str_list))

TLEした後は、リストをアルファベット順にして探索範囲を抑えればいいとか考えたけど、重複リストの高速化なんてどっかにネットに落ちてるだろという安易な考えてGoogle検索しました。

Pythonで"in list"から"in set"に変えただけで爆速になった件とその理由 - Qiita

「Pythonで"in list"から"in set"に変えただけで爆速になった件とその理由」というタイトルの記事ですが、めちゃくちゃわかりやすい。 重要な部分だけまとめると、list()で書かれるリスト構造は全探索が必要である一方、set()で書かれる集合型(?)はハッシュテーブルで書かれるため、ハッシュ値だけ探索すれば良いので高速らしいです。

提出したプログラム

# https://atcoder.jp/contests/abc164/submissions/12363327

N = int(input())
str_list = []

for i in range(N):
    n = input()
    if n in str_list:
        continue
    else:
        str_list.append(n)
print(len(str_list))

set型が287msで、list型が2207msと信じられないくらい速くなりました。