ABC350を解いた際の考え方と解説を読んだアウトプット
結果:C問題まで着手したが、解けたのはA問題のみ
A - Past ABCs
考え方
1以上350未満かつ316でない場合はYesを返す
ABC000に引っかかってしまった
B - Dentist Aoki
考え方
1回目:setを用いて重複を消し、総数 - 治療回数 + setの中身の数で回答
入力例3のようなものでマイナスの値を取ってしまう
考え方2
bool型のバケツを作り、バケツに入った数が答えとする
入力されるたびに判定をすることで回答を導き出すことができた
解説を読んで
自分はif文で制御していたが、0と1の入れ替えをする際にxorを用いる実装方法を知ることが出来た
C - Sort
考え方1
ソート手法に入れ替えた回数と入れ替え部分を記録した
用いたアルゴリズムが*O(N^2)*となるため、TLEしてしまった
考え方2
swapを用いて入れ替える
swapを使うのはいいが、入れ替えた数字をメモすることを考えていたら手が止まってしまった(単なる実力不足ですね)
解説を読んで
線形代数で見たことあるやつを使っていて感動した(小並感)
数字の存在位置を示す配列を別途で用意することで処理回数を減らすことができるのは目から鱗だった
D - New Friends
考え方
連結可能なノードを探して数え上げる
言うのは簡単ですね(実力不足でした)
解説を読んで
考え方は合っていた、嬉しい
他の人の回答を見て
ngtkanaさんの回答より
RustにもUnionFindのライブラリがあるんやなぁ、、、
ドデカメモ
RustでのUnionFindの使い方
https://qiita.com/illumination-k/items/6fe0e91d4681fe48ab8e
↑参照
use petgraph::unionfind::UnionFind;
let mut uf = UnionFind::new(); //UnionFindの宣言と初期化
uf.union(a,b); //aとbのグループを結合
let flag:bool = uf.equiv(a,b); //aとbが同じグループに属するか判定