AtCoder Beginner Contest 166を振り返る

Pythonで挑戦しました。

A - A?C

"ARC"か”ABC”が入力されるので、入力されなかった方を出力する問題
私は以下の様に解きました。

print("ABC" if input() == "ARC" else "ARC")

実行速度見ると上記記述だと23msですが、以下だと19msになる様です。

if input() == "ABC":
   print("ARC")
else:
   print("ABC")

可読性も高いのでこっちの方がいいかもしれないですね。

B - Trick or Treat

ユーザーの人数(N)と以下の行数(K)が与えられた後に、複数行に渡ってユーザーID（1,2,3,4,...N）が複数列で入力されるので、入力されなかったユーザーIDの数を出力する問題（意訳）
以下の様に解答しました。

N, K = map(int, input().split())
sunukes = [1 for _ in range(N)]
for _ in range(K):
   d = input()
   owner_list = [int(i) for i in input().split()]
   for owner in owner_list:
       sunukes[owner-1] = 0
print(sum(sunukes))

こう言った感じで、先にユーザーを表す枠を用意して、入力されるIDに応じて対象のユーザーステータスを変更し、最後に数え上げると言う方法と以下の様に

N, K = map(int, input().split())
uid_list = []
for _ in range(K):
   input()
   for uid in [int(i) for i in input().split()]:
       uid_list.append(uid)
print(N - len(set(uid_list)))

ユーザーIDの入れ物を作ってとりあえず全部登録し、最後に一意の値の数を総数からひく方法を取ってる人が多い印象ですね。どっちがいいとかはよくわからんですが、2つ目は思いつかなかったので面白い。

C - Peaks

AtCoder丘陵には N 個の展望台があり、展望台 i の標高は Hi です。
また、異なる展望台どうしを結ぶ M 本の道があり、道 j は展望台 Aj と展望台 Bj を結んでいます。展望台 i が良い展望台であるとは、展望台 i から一本の道を使って辿り着けるどの展望台よりも展望台 i の方が標高が高いことをいいます。 展望台 i から一本の道を使って辿り着ける展望台が存在しない場合も、展望台 i は良い展望台であるといいます。
良い展望台がいくつあるか求めてください。

という問題、私は展望台のリストを作成し、道で結ばれた展望台以下の標高だった場合はリストのステータスを変えて、リストに含まれる良い展望台の数を確認すると言う方法で回答しました。コードは以下です

N, M = map(int, input().split())
p_list = [1 for _ in range(N)]
e_list = list(map(int, input().split()))
for _ in range(M):
   a, b = map(int, input().split())
   if e_list[a - 1] <= e_list[b - 1]:
       p_list[a - 1] = 0
   if e_list[b - 1] <= e_list[a - 1]:
       p_list[b - 1] = 0
print(sum(p_list))

他には以下の様に、展望台毎に道で結ばれた展望台のリストを作成しそのリストで高さを比較し良い展望台をカウントアップすると言う解法もある様です。

N, M = map(int, input().split())
c_list = [[] for _ in range(N)]
e_list = list(map(int, input().split()))
for _ in range(M):
   a, b = map(lambda i: int(i) - 1, input().split())
   c_list[a].append(b)
   c_list[b].append(a)
ans = 0
for i, e in enumerate(e_list):
   for j in c_list[i]:
       if e <= e_list[j]:
           break
   else:
       ans += 1

print(ans)

まとめ

今回は、Dは予想がつかずEは総当たりで解決しようとしたら、時間超過してしまいました。解説PDFでもよくわからなかったので、解説動画が公開されたら確認してみようと思います。解説がC++で書かれているのでかけなくてもいいから、読める様になりたいものだ。。。