AtCoder ABC 168

ABC3完の茶色パフォでした。今回のレベルでDまで行けなかったのは不甲斐ないので、改めて精進したい。

A - ∴ (Therefore)

問題のリンク

概要

• の一の位で場合分け

制約

• は以下の正の整数

考察

特になし

コード

N = input()

if int(N[-1]) in [2,4,5,7,9]:
    print('hon')
elif int(N[-1]) in [0,1,6,8]:
    print('pon')
else:
    print('bon')

B - ... (Triple Dots)

問題のリンク

概要

• 文字列の長さで場合分け

制約

• は以上、以下の整数
• は英小文字からなる文字列
• の長さは以上、以下

考察

特になし

コード

K = int(input())
S = input()

if len(S)<=K:
    print(S)
else:
    ans = S[:K] + '...'
    print(ans)

C - : (Colon)

問題のリンク

概要

• ある時計の長針の長さ、短針の長さ、及び現時刻が与えられた時の長針の先端と短針の先端の距離

制約

• 入力は全て整数
• 
• 
• 

考察

　三平方の定理をググれば理論上はすぐに解ける問題。だが当初、短針の角度を(H/12) * 360)としてしまっており、計算が合わず時間をロスしてしまった。正しくはminuteも考慮した((H/12) * 360) + (30*(M/60))。これに気づくまでに時間がかかってしまった。今後は気を付けたい。

コード

import math

A, B, H, M = map(int, input().split())

ka_a = ((H/12) * 360) + (30*(M/60))
ka_b = M/60 * 360

kakudo = max(ka_a, ka_b) - min(ka_a, ka_b)
kakudo = min(kakudo, (360-kakudo))
cos = math.cos(math.radians(kakudo))

if kakudo==180:
    print(A+B)
    exit()

ans = A**2 + B**2 - 2*A*B*cos

print(math.sqrt(ans))

D - .. (Double Dots)

問題のリンク

概要

• いわゆる最短経路問題
• 最短経路を通った際、次に進む先のノードの番号を求める

制約

• 入力は全て整数
• 
• 
• 
• 
• どの部屋間も、道路をいくつか通って行き来できる

考察

• 根(番目の部屋)をスタートに幅優先探索をしていく
• 制約上、どの二部屋間も行き来できる（つまり必ず1のゴールにたどり着けるという保証がされている）ので、Noの答えはあり得ない。つまり、探索すべきグラフは必ず一つしかあり得ない。

コード

from collections import deque

def bfs_tree(graph, v=1):
    """
    graph: グラフ
    v: スタート
    """
    # 矢印がどこを向いているか
    # -1だと未探索
    arrow = [-1]*len(graph) 
    q = deque()
    q.append(v)
    arrow[v] = 0
    while q:
        now = q.popleft()
        for next_v in graph[now]:
            if arrow[next_v] != -1:
                continue
            else:
                q.append(next_v)
                arrow[next_v] = now
    return arrow

N, M = map(int, input().split())
graph = [[] for _ in range(N)]
pre = []

for _ in range(M):
    A, B = map(int, input().split())
    graph[A-1].append(B-1)
    graph[B-1].append(A-1)

arrow = bfs_tree(graph, 0)

print('Yes')
for i in range(1, N):
    print(arrow[i]+1)