AtCoder Beginner Contest 166 備忘録

AtCoder Beginner Contest 166の備忘録です。

問題文はこちら↓

AtCoder Beginner Contest 166 - AtCoder

今回はABCD4完でした。

・A問題:A?C

入力が”ABC”なら”ARC"、”ARC"なら”ABC"を出力する。

解答例(Python)
https://atcoder.jp/contests/abc166/submissions/12786810

・B問題:Trick or Treat

N人の人 (1~N) がおりK種類のお菓子があり、お菓子 Ai は Ai1 ~ Aidi の計 di 人が持っている。
N人のうちお菓子を1つも持っていない人数を数える。
お菓子を持っている人をsetで持ち、1~Nのうちsetに含まれていない数を数える。

解答例(Python)
https://atcoder.jp/contests/abc166/submissions/12788439

・C問題:Peaks

N 箇所の展望台があり展望台 i の標高が Hi、また展望台を結ぶ道が M 本あり、道 j は展望台 Aj と Bj を結んでいる。展望台から伸びている道を1つだけ通って行ける展望台のうち最も高い展望台を良い展望台と呼び、それがいくつあるか求める。
N 箇所の展望台 i に対応するように配列を作り各展望台から道が繋がっている展望台をsetで持つ。配列を順番に見ていき、見ている展望台とsetが持っている展望台の高さを比較し、最も高ければ答えを1増やす。

解答例(Python))
https://atcoder.jp/contests/abc166/submissions/12789146

・D問題:I hate Factorization

A^5-B^5=Xを満たす整数の組(A,B)を求める。
Aを固定してBを二分探索して、一致すればA,Bを出力する。しなければAを増やしてBを二分探索する。これを式を満たすまで繰り返す。

解答例(Python)
https://atcoder.jp/contests/abc166/submissions/12790230