ABC168 復習

ABC AtCoder Python

D問題まで解けました！
幅優先探索の典型的なパターンだったので、勉強した甲斐がありました。
と、いうわけで復習です。

atcoder.jp

A - ∴ (Therefore)

ポイントは2つ、

  • 文字列の末尾を取得する
  • 取得した文字列によって挙動を変える（ifが書ける）

いつものように、初心者問題ですね。

n = input()

if n[-1] == '3':
    print('bon')
elif n[-1] in '24579':
    print('hon')
else:
    print('pon')

B - ... (Triple Dots)

こちらもA問題とほぼやることは変わらず、A問題の知識に加えて「文字列の連結」ができれば解けます。

k = int(input())
s = input()

if len(s) <= k:
    print(s)
else:
    print(s[:k] + '...')

C - : (Colon)

個人的に今回解いた中では一番難しかったです。
この問題を解くには、

  1. 入力で与えられた時刻から長針・短針の間の角度を求める
  2. 入力値の三角形の2辺と求めた角度を元に残りの1辺を求める（余弦定理というらしい）

の2つをクリアする必要があります。

import math
a, b, h, m = map(int, input().split())

# 角度を割り出す
hour = m * (360 // 60)
minutes = h * (360 // 12) + (0.5 * m)

angle = 0
if abs(hour - minutes) > 180:
    angle = 360 - (abs(hour - minutes))
else:
    angle = abs(hour - minutes)

ans = ((b ** 2) + (a ** 2)) - (2 * a * b * math.cos(math.radians(angle)))

print(math.sqrt(ans))

D - .. (Double Dots)

この問題は正直一度でも幅優先探索を解いたことがある（勉強したことがある）方ならおそらく解けたんじゃないかと思います。

ほとんど教科書通りの幅優先探索を書くだけです。
1点、注意しないといけないのは通常の幅優先探索では各地点への最短距離（移動回数）を求めるのが多いですが、今回の問題ではどこから来たのかを答えとして持つ必要があります。
とはいえ、最短距離を求める場合においてもどこから来たのか（1つ前の地点までの最短距離はいくつか）を持ちつつ処理を行うので、少し改造すれば解けると思います。

from collections import deque
n, m = map(int, input().split())

# 1_indexにする
dist = [-1] * (n + 1)
roots = [[] for i in range(n + 1)]

for i in range(m):
    a, b = map(int, input().split())
    roots[a].append(b)
    roots[b].append(a)

ans = [-1] * (n + 1)
ans[1] = 0
dist[1] = 0
q = deque()
q.append(1)

while q:
    now = q.popleft()

    for next_v in roots[now]:
        if not dist[next_v] == -1:
            continue
        dist[next_v] = dist[now] + 1
        # ここで、どこから来たのかを保持する
        ans[next_v] = now
        q.append(next_v)
#行けていない場所がある場合
if -1 in ans[1:]:
    print('No')
else:
    print('Yes')
    for i in range(2, len(ans)):
        print(ans[i])

E - ∙ (Bullet)

E問題はチャレンジすらしていません・・。
まぁ今日はD問題までとけたから良しとしよう。