ACL Beginner Contestの感想
略称はABLらしい。明日から使えるムダ知識をあなたに
100-200-300(1)-0-0-0で1ペナ3完600点。
A - Repeat ACL
ACLという文字列を回だけ出力する。
は5パターンしかないのでif文を用いて5通りの分岐を記述すると解ける。また、ループを用いると問題文の処理をそのまま実装できるので楽。
計算量は、。
B - Integer Preference
以上
以下の範囲を
、
以上
以下の範囲を
と呼ぶことにする。
2人が好きな整数が存在するということは、範囲と範囲
が重なっているということ。ここで、①「範囲
の最大値が範囲
の最大値より小さい」と仮定すると、範囲
の最大値が範囲
の最小値より大きければ重なっていることがわかる（等しくても重なる）。これは入力の数値を用いて表現すると
で判定できる。もし①の条件を満たしていないなら
と
、
と
を入れ替えることで同様の判定式で判定できる。
計算量は、。
C - Connect Cities
都市を頂点、道路を辺と見たグラフを考える。1回の操作により、異なる2つの連結成分*1 を辺でつなぐことができる。初めの状態で連結成分が個あるなら、この操作を
回行えば必ず連結成分が1個になるので、答えは
である。
あとは連結成分の個数を数えられれば良い。これにはDFSを用いて全頂点を走査する方法や、UnionFindで頂点集合を管理する方法がある。今回はUnionFindを用いて実装した。
ACLでは、UnionFindという名前ではなく「DSU（Disjoint Set Union）」と呼ばれている。同じ集合に属するならばその集合の代表元も同じなので、setなどを用いて代表元の個数を数える。
計算量は、DFSを用いる方法で、UnionFindとsetを用いる方法で
。
E - Replace Digits
遅延セグ木を使うとで書ける。
感想
水色なのに茶パフォとってしまったのでしばらく謹慎する
*1:無向グラフにおいて、辺でつながっている頂点のまとまりのこと
