[PythonでAtcoder] AtCoder Beginner Contest 168 解説

自分用の勉強記録もかねて、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は基本的なアルゴリズムなので是非押さえましょう！