読者です 読者をやめる 読者になる 読者になる

srupのメモ帳

競プロで解いた問題や勉強したことを記録していくメモ帳

ARC 032 B - 道路工事

問題 問題概要 省略。 解法 union find を使って、連結成分がいくつできているjかを数得ればよい。連結成分を1つにするのに必要な辺の数は答えになるので、答えは(連結成分の数-1)となる。 ミス なし。 コード #include <bits/stdc++.h> using namespace std; typedef long</bits/stdc++.h>…

ARC 031 B - 埋め立て

問題 問題概要 盤面上での陸地の繋がりを調べえる問題。ただし、1マス分だけ陸地にすることができる。 解法 10x10の盤面で小さいので、100個あるマスを1つ変えた時に、どうなるかを調べる。全探索するということ。 回りの4方向で陸どおしでつながっている部…

yukicoder No.416 旅行会社

問題 問題概要 省略 解法 union findは辺を削除することができない。問題は、クエリを与えられた順にみると、辺を削除するような形だが、クエリを逆からみれば、辺をつなげていく形になる。このようになると、union findで管理できる。 また今回学んだunion …