1/11(月)
ABC177 D-frinends
ABC075 C-Bridge を解いた。どちらもUnion Findが使える典型的な問題だった。気を付けることとしてグループの単位となる数字を--することを忘れずに。
1/12(火)
ARC032 B-道路工事 , 037 B- バウムテスト を解いた。道路工事はできたグループの数を調べればいいだけで、これは配列parのうち、i=par[i]となっている数を数えればよい。バウムテストのほうはややてこずった。閉路ができている場合は、根のおおもととなる部分が複数あるのではないか、と思ったがそんなことはなかった。unite(x,y)はxとyの大本となる部分を調べて、それぞれの木の長さが小さいほうを大きいほうにくっつけるという関数である。つまり根の大本同士をくらべ1つにしているから大本の根は1つしか存在しない。
1/15(金)
あやうく3日坊主となるところだったがギリ回避。ARC097D-Equalsを解いた。ペアをグラフで考えてそれをUnionFindを使うっていう応用問題だったがこの前解けなかったARCの問題にそっくりなので一瞬だった。