ACL Beginner Contest 備忘録

ACL Beginner Contestの備忘録です。

問題はこちら↓

ACL Beginner Contest - AtCoder

今回はABC3完でした。

・A問題:Repeat ACL

整数 K が与えられるので、文字列 'ACL' を K 回繰り返した文字列を出力する。

解答例(Python)
https://atcoder.jp/contests/abl/submissions/17047109

・B問題:Integer Preference

A 以上 B 以下かつ C 以上 D 以下の整数が存在するか調べる。

解答例(Python)
https://atcoder.jp/contests/abl/submissions/17047305

・C問題:Connect Cities

N 個の都市(1~Nまで)と M 個の双方向道路(1~Mまで)があり、道路 i は都市 Ai と都市 Bi を結ぶ。
以下の操作を 0 回以上行う。

・道路で直接結ばれていない2つの異なる都市の間に道路を作る

操作を終えた後、どの都市からどの都市へも道路を辿ることで到達できるようにしたい。
この時、最低何個の道路を作ればよいか求める。
初期状態をグラフとして考えると、繋がっていないグラフを繋ぐために必要な辺の数を求めることになるので、まず繋がっていないグループの数を数える。そのためにまず各都市に訪れたかどうか記録する配列を用意し、まだ訪れていない都市がある間ループを回す。ループの中で Queue を用意し、今いる都市から移動できる都市のうちまだ訪れていない都市を格納していく。ループが1巡した後にまだ訪れていない都市があれば ans を1増やしもう一度繰り返す。全ての都市に訪れた後は ans を増やさずに出力すればよい。

解答例(Python)
https://atcoder.jp/contests/abl/submissions/17048309