Atcoder-ABC201をpythonで問題を解いてみた

目的

• Atcoderで上を目指すべく頑張っている中でABC201を解いたので、解説してみる
  • pypy7.3を使って解いている

A問題

atcoder.jp

考察

• 与えられた数列Aの要素を全て並び替えて、確認する
  • 3!で6通りなので全て試せばよさそう

実装

from itertools import permutations

A = list(map(int, input().split()))

flag = False

for a1, a2, a3 in permutations(A):
    if a1-a2 == a2-a3:
        flag = True
        break

if flag:
    print("Yes")
else:
    print("No")

結果

• 無事に解けた

B問題

atcoder.jp

考察

• (山の名前, 山の高さ) の配列を作り、山の高さでsortし、2番目に高いものを出せばよさそう
  • pythonなら、sortするkeyを指定できる

実装

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

for _ in range(N):
    S, T = input().split()
    T = int(T)
    ST.append((S, T))

# 山の高さでsortする
sorted_ST = sorted(ST, key=lambda x: x[1])
print(sorted_ST[-2][0])

結果

• 無事に解けた

C問題

atcoder.jp

愚直に全探索するべきなのに、場合の数とか考えて集合とかで数えられないかなと考え出してドツボにハマり時間切れした・・・

考察

• 必ず使われる数字の種類と、使われてるかもしれない数字の種類で考えて場合分けできそうだなと思って解いていた
  • 実際、解けなくもなさそうだけど、自分はゴチャゴチャになって解けなかったww

blog.hamayanhamayan.com

• そもそも、パスワードのパターンは10000通りしかないので、条件に合致するものを全て調べあげた方がシンプル
  • パスワードには、使われる数字の種類が、全て使われているか？
  • パスワードには、使われていない数字が、含まれてないか？

実装

S = input()

used = S.count("o")

ans = 0
for i in range(10000):
    passwd = str(i).rjust(4, "0")
    cnt, flag = [False]*10, True
    for j in range(4):
        k = int(passwd[j])
        if S[k] == "o":
            cnt[k] = True
        elif S[k] == "x":
            flag = False
    if cnt.count(True) == used and flag:
        ans += 1
print(ans)

結果

• 無事に解けた