AtCoder Beginner Contest 168 備忘録

AtCoder Beginner Contest 168の備忘録です。

問題はこちら↓

AtCoder Beginner Contest 168 - AtCoder

今回はABCD4完でした。

・A問題:∴ (Therefore)

鉛筆を数える時の「本」の読み方を出力する。
N を10で割った余りが 2,4,5,7,9 の時 'hon'、0,1,6,8 の時 'pon'、3の時 'bon' を出力する。

解答例(Python)
https://atcoder.jp/contests/abc168/submissions/13290583

・B問題:... (Triple Dots)

文字列 S が与えられ、S の長さが K 以下であれば S をそのまま出力、K よりも長ければ先頭の K 文字とその末尾に '...' をつけた文字列を出力する。
文字列 S から先頭の K 文字を T として、S と T を比較し同じであれば S を出力する。違う場合は T... と出力する。

解答例(Python)
https://atcoder.jp/contests/abc168/submissions/13296309

・C問題: : (Colon)

時針と分針の長さがそれぞれ A cmと B cmのアナログ時計があり、ある時間の時のそれぞれの針の端がどれだけ離れているか求める。
分針は1分でに6°(360°/ 60°)動くので H * 6 °動いたところにある。時針は1時間で30°(360°/12°)動く。しかし時針は1時間かけて動いていくので0°以上30°未満の端数が生じる。これは 30 * (H / 60) で求められる。これらの移動した角度の差が針の間の角度になる。
あとは余弦定理から、求めたい辺の長さ X は間の角度を R として

sqrt(A^2+B^2-2*A*B*cosR)

で求める事ができる。この時、先に求めた角度の差が180°を超えてしまう場合は
R = 360-R とすることに注意する。

解答例(Python)
https://atcoder.jp/contests/abc168/submissions/13349531

・D問題:.. (Double Dots)

N 個の部屋と M 本の通路があり、部屋には1~N、通路には1~Mの番号が付いている。通路はそれぞれ2つの部屋を繋いでいて、いくつかの通路を通ってどの部屋にも行き来する事ができる。
部屋1以外の全ての部屋に、部屋1へ最小の移動回数で辿り着けるような直接繋がっている部屋の番号を設ける。
このような道しるべの配置が存在するか判定し、存在すればそのような配置を1つ出力する。
部屋1から順に探索していき、未探索の部屋に今いる部屋の番号を設定していくようにする。このような処理は 幅優先探索(BFS) で行う事ができる。
BFSを行う為に queue をインポートしておく。queue は先入れ先出し(FIFO)できるデータ構造である。
まず queue に部屋1を入れておき、while ループで queue が空になるまで繰り返す。ループ内で queue の先頭を取り出しそこから繋がっていて未探索の部屋があればその部屋に取り出した部屋の番号を設定し、未探索の部屋の番号を queue に追加する。繋がっている未探索の部屋が無くなったらまた queue から先頭を取り出して同様に処理していく。
全て探索が終わったら部屋1以外の部屋に設定した番号を順番に出力する。
どの2部屋間もいくつかの通路を通って移動できるので、必ず部屋1へ最短で移動できる経路が存在する為判定は必要ない。

解答例(Python)
https://atcoder.jp/contests/abc168/submissions/13351956