自分用の勉強記録もかねて、Atcoderの解説をしていきたいと思います。
今回は、ABC完答でした。A~Cは問題文の通りに実装すればよいかなというかんじでした。Dについては、今勉強中の数え上げ・探索の問題でしたので、いい勉強になりました。
A~Dについて解説していきます。
僕もプログラミングについて絶賛学習中なので、間違え等ございましたら気軽にご連絡ください。
A ∴ (Therefore)
問題はこちら
n = input()
n_1 = int(n[-1])
if n_1 == 3:
print('bon')
elif n_1 == 0 or n_1 == 1 or n_1 == 6 or n_1 == 8:
print('pon')
else:
print('hon')条件分岐の書き方はいろいろあると思いますが、自分は最初上のコードを書いて、短くしたいなと思い、集合の概念のコードを使いました。
elif {n_1} <= {0,1,6,8}:B - ... (Triple Dots)
問題はこちら
k = int(input())
s = input()
num = len(s)
if num <=k:
print(s)
else:
print(s[:k]+'...')素直に実装するだけという印象です。
C - : (Colon)
問題はこちら
import math
a,b,h,m = map(int, input().split())
mi = m + h*60
x = 2*math.pi /(12*60)
y = 2*math.pi /60
an = abs(x-y)*mi
c = math.sqrt(a**2 + b**2 - 2*a*b*math.cos(an))
print(c)余弦定理を使って実装していけばよいですね。
D - .. (Double Dots)
問題はこちら
いろいろグラフを書いていくと、幅優先探索 (breadth-first search, 以下BFS) で解けることに気づくとよいですね。
僕は、BFSの知識がなかったですし、Noが出力される場合とか考えていました。（Noが出力される場合はありません。）
BFSはキュー（queue）というデータ構造を使うと実装することができます。
Pythonでは、queueやdequeというモジュールを使えば実装できますし、モジュールを使わずにlistだけで書くこともできます。
※dequeはキューとスタックを併せ持つデータ構造です。
今回は他の方のコードを参考にdequeを使った場合とlistのみで書いた場合の2通りを紹介します。
・モジュール dequeを使う場合
from collections import deque
n, m = map(int, input().split())
ab = [list(map(int, input().split())) for _ in range(m)] #Ex.ab = [[A1,B1],[A2,B2],…[]]
ans = [-1 for _ in range(n)] # 道標を記録。最後にこれを出力。
ans[0] = 0
tree = [[] for _ in range(n)] # 部屋間のつながりを記録
for a, b in ab:
tree[a-1].append(b-1)
tree[b-1].append(a-1)
# Ex. tree = [[2,4][3]…[]]
q = deque([0]) #キュー。次に探索する部屋を記録していく。最初は0が格納。
while q: #キューが空になれば終了。
p = q.popleft() #キューなので左から取り出す。
for i in tree[p]:
if ans[i] < 0: # visit[i] >= 0なら既に探索しているので無視。
ans[i] = p
q.append(i) #新たにキューに加える。
print("Yes")
for i in ans[1:]:
print(i+1)参考：https://atcoder.jp/contests/abc168/submissions/13313098
・listのみで書いた場合
n, m = map(int, input().split())
ab=[list(map(int,input().split())) for _ in range(m)]
ans = [-1 for _ in range(n)]
ans[0] = 0
tree=[[]for _ in range(n)]
for a,b in ab:
tree[a-1].append(b-1)
tree[b-1].append(a-1)
visited={0}
q=[0] # キュー
for i in q:
for j in tree[i]:
if ans[j] < 0:
q.append(j)
ans[j]=i+1
print("Yes")
for i in ans[1:]:
print(i)BFSは基本的なアルゴリズムなので是非押さえましょう！
コメント