けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

連結成分

JOIG 2023 E - 運河 (難易度 7)

UnionFind を使って、差分更新を頑張る! UnionFind はオンラインの処理を簡単に実現できることが強みで、それを問いかける教育的問題ですね。他にも「左右からの結果を前処理する」という典型テクも使います! 問題へのリンク 問題概要 のグリッドがあって…

AtCoder ABC 325 C - Sensors (茶色, 300 点)

またまた登場!! グラフの連結成分の個数を求める問題! 問題へのリンク 問題概要 下図のような のグリッドが与えられる。このグリッドにおいて、上下左右と斜めに隣接している '#' は一つの塊とみなす。 このとき、グリッド内に何個の '#' の塊があるかを…

AtCoder ABC 284 C - Count Connected Components (灰色, 300 点)

グラフ探索の問題として、人生で最初に解きたい問題!! 問題へのリンク 問題概要 頂点数 、辺数 の単純な無向グラフが与えられる。 このグラフの連結成分の個数を求めよ。 制約 解法 まず、単純グラフや連結成分という概念についてはこちら! algo-method.c…

AtCoder ABC 321 G - Electric Circuit (橙色, 600 点)

除原理! 学びの多い問題だった。Subset Convolution の方はちょっと頑張ってこの後復習する。 問題へのリンク 問題概要 頂点番号が であるグラフ がある。最初、辺は 1 本もない。 以上 以下の値からなるサイズ の 2 つの数列 と がある。 今、これら 2 つ…

AtCoder ARC 143 D - Bridges (黄色, 700 点)

二重辺連結成分分解とか low-link とか色々考えたけど、結果的に最後は「ただ DFS 木を作るだけ」になるという、すごく印象的な問題! 問題へのリンク 問題概要 以上 以下の整数からなるサイズ の 2 つの数列 、 が与えられる。 今、0 と 1 のみからなるサイ…

AtCoder ABC 256 E - Takahashi's Anguish (水色, 500 点)

最近話題の Functional Graph の問題! 問題へのリンク 問題概要 人 がいる。各人 には 1 人ずつ嫌いな人 がいる。 今、彼らに順番にキャンディーを配る。ただし、各 について、もし人 よりも先に にキャンディーを配ると、不満度が だけ加算される。 キャン…

AtCoder ARC 031 B - 埋め立て (試験管緑色)

今なお色褪せることのない、DFS・BFS の入門にいい感じの練習問題!!! 問題へのリンク 問題概要 次のような、 のサイズのグリッドの入力が与えられます。各マスの文字は 'o' か 'x' かのいずれかです。 あなたは、グリッド内部の文字を 1 つ選んで 'o' に…

AtCoder ABC 277 C - Ladder Takahashi (茶色, 300 点)

グラフで考えよう! 問題へのリンク 問題概要 階建てのビルがあります。 ハシゴが 個あり、 個目のハシゴは 階と 階を結んでいます。これらのハシゴは双方に行き来できます。ただし、ハシゴ以外の手段によって、異なる階の行き来はできません。 高橋くんは最…

AtCoder ABC 304 E - Good Graph (緑色, 475 点)

Union-Find 慣れしていれば解きやすい! 問題へのリンク 問題概要 頂点数 、辺数 の無向単純グラフ が与えられる。 組の頂点対 について、どの頂点対間のもパスがないグラフを良いグラフと呼ぶことにする。 与えられるグラフ は良いグラフである。 このグラ…

AtCoder ABC 304 C - Virus (灰色, 300 点)

単純な DFS / BFS 系はいよいよ灰色 diff になったのですね。 問題へのリンク 問題概要 二次元平面上に 人がいます。 番目の人は座標 にいます。 今、 番目の人がウィルスに感染しました。ウイルスに感染した人から距離が 以内にいる人にウイルスは次々とう…

AtCoder ABC 300 C - Cross (茶色, 300 点)

実装が難しい系。僕は DFS をした。「島の個数」を数える問題なので、何も考えずに DFS すればいいと思った。 問題へのリンク 問題概要 下図のような のグリッドの入力が与えられる。 「# で作られた x の形からなる島」が何個あるかを、島の大きさごとに答…

AtCoder ABC 282 D - Make Bipartite 2 (緑色, 400 点)

一般にグラフの問題を解くときは「連結成分ごとに解けば良いのではないか」と考えるのが有効なことがある! その意識がしっかりしていれば、「グラフが非連結の場合に気づかなかった」という罠を回避できる!! 問題へのリンク 問題概要 頂点数 、辺数 の単…

AtCoder ABC 049 D - 連結 (ARC 065 D) (青色, 400 点)

Union-Find を上手に使うと解けるいい練習問題ですね。 問題へのリンク 問題概要 個の都市があって、都市間を 本の「道路」と 本の「鉄道」が結んでいる。各道路と各鉄道は、結んでいる都市間を双方向に移動することができる。 各都市 に対して、以下の条件…

AtCoder ABC 075 C - Bridge (緑色, 300 点)

Union-Find や、DFS、BFS などで解ける問題ですね。 問題へのリンク 問題概要 頂点数 、辺数 の連結な単純無向グラフ が与えられます。 グラフ の辺 が橋であるとは、その辺を除去したときに、グラフが連結でなくなることを指すものとします。 グラフ におい…

AtCoder ABC 206 D - KAIBUNsyo (緑色, 400 点)

今や Union-Find やるだけだと茶色 diff (下手したら灰色 diff) だけど、ちゃんと考察要素を入れるとやっぱり緑色 diff になるのね。 問題へのリンク 問題概要 正の整数からなる整数列 が与えられる。以下の操作を好きなだけ行うことによって、 個の値がすべ…

AtCoder ARC 115 D - Odd Degree (黄色, 600 点)

なんとか解けた。若干エスパー気味に解いた。 問題へのリンク 問題概要 頂点数 、辺数 の無向単純グラフが与えられる。 各 に対して、この誘導部分グラフ (頂点集合はそのまま、辺集合は部分集合) であって、次数が奇数の頂点が 個であるようなものの個数を …

JOI 春合宿 2007 day4-1 Fiber (難易度 5)

無向グラフの連結成分の個数を数える問題 ジャッジへのリンク 問題へのリンク 問題概要 頂点数 、辺数 の無向グラフが与えられる。このグラフにいくつかの辺を新たに追加することによって、グラフ全体が連結となるようにしたい。 追加すべき辺の本数の最小値…

JOI 予選 2012 E - イルミネーション (AOJ 0569, 難易度 6)

ハニカムつらい 問題へのリンク editorial 問題概要 下図で表されるようなハニカム状のグリッドが与えられる (図は問題文より)。 黒色マスは建物があるマスを表している。赤太線は、「外側」から見て見える外壁を表している。 このような のマップが与えられ…

Codeforces Round #683 (Div. 1) C. Xor Tree (R2100)

こどふぉのこの回、いい問題が多かった気がするので解き直し。最上位の桁から順に見ていって、0 と 1 とに分類していって...とするのはよく見る気がする!!! 問題へのリンク 問題概要 どの要素も互いに相異なる非負整数列 が good であるとは、以下の条件…

Codeforces Round #681 (Div. 1) E. Black, White and Grey Tree (R3000)

最初まんまと罠にひっかかった 問題へのリンク 問題概要 頂点数 の木が与えられる。各頂点には 0, 1, 2 のいずれかの色 (0: 灰色, 1: 白色, 2: 黒色) が割り振られている。以下の操作を最小回数行うことで、木を消滅させたい。最小回数を求めよ。 [操作]:残…

AtCoder ABC 181 F - Silver Woods (黄色, 600 点)

条件反射で二分探索してしまった!!!この問題めっちゃ面白くて好き!!! 問題へのリンク editorial 問題概要 平面上に 2 直線 で囲まれた通路がある。この通路の中の の部分に 本の大きさの無視できる釘が打たれており、 本目の釘の座標は である。 高橋…

AtCoder ARC 106 B - Values (茶色, 400 点)

問題へのリンク 問題概要 頂点数 、辺数 の無向グラフが与えられる。各頂点 には値 が書かれている。以下の操作を好きな順序で好きな回数だけ行うことで、各頂点 の数値が であるような状態にすることが可能かどうかを判定せよ。 辺 を選んで、以下のいずれ…

AtCoder ABC 180 F - Unbranched (橙色, 600 点)

結構いろんな考え方のできる問題! 問題へのリンク 問題概要 頂点数 、辺数 の無向グラフであって、次の条件を満たすものの個数を 1000000007 で割ったあまりを求めよ。 自己ループを持たない すべての頂点の次数が 2 以下である 各連結成分のサイズを並べた…

AOJ 2376 DisconnectedGame (JAG 冬合宿 2010 day3-H) (600 点)

こないだの ARC でめっちゃ似た問題が出たので!これは、SolveMe を含む、りんごさんによる伝説のセット。 drken1215.hatenablog.com 問題へのリンク 問題概要 頂点数 のグラフが与えられる (入力は の隣接行列で与えられ、初期状態では非連結である)。この…

AtCoder ARC 105 E - Keep Graph Disconnected (橙色, 700 点)

とてもシンプルな設定で面白かった!でもバグらせてそうで、提出するのは怖かった。 問題へのリンク 問題概要 頂点数 、辺数 の単純無向グラフが与えられる。初期状態では頂点 1 と頂点 は非連結である。 先手と後手が、交互に 1 本ずつ辺を追加していく。た…

AtCoder ABC 177 D - Friends (茶色, 400 点)

Union-Find の典型的な問題!! でも、DFS や BFS でも解くことができる。 問題へのリンク 問題概要 人 から 人 までの 人の人がいます。 「人 と人 は友達である」という情報が 個与えられます。同じ情報が複数回与えられることもあります。 と が友達、か…

ACL Beginner Contest C - Connect Cities (茶色, 300 点)

Union-Find の練習問題という雰囲気ながら、DFS や BFS でも解ける 問題へのリンク 問題概要 頂点数 、辺数 の単純無向グラフが与えられる。これに最小本数の辺を追加することで全体が連結となるようにしたい。その最小本数を求めよ。 制約 考えたこと 全体…

ACL Contest 1 A - Reachable Towns (水色, 300 点)

えーーー、300 点!? 問題へのリンク 問題概要 二次元平面上に 点が与えられる。これらの点の x 座標、y 座標を抽出すると、それらは の順列となっている。 各 に対して、点 から 自分よりも x 座標と y 座標がともに大きな点 自分よりも x 座標と y 座標が…

AOJ 3178 Katsusando (HUPC 2020 day3-G)

いわゆる区間分割する系の DP。こういう系は高速化を要求するタイプの問題が多いけど、今回は素直な二乗 DP で OK! 問題へのリンク 問題概要 直線上にカツが 個ある。 個目のカツは位置 にあり、その重さは である。これらのカツを、次のようにしてすべて回…

AOJ 3183 Flipping a Path (HUPC 2020 day3-L)

こういう系すごく楽しいよね 問題へのリンク 問題概要 頂点数 、辺数 の重み付き有向単純グラフ が与えられる。 このグラフ上で次の条件を満たすパス (同じ頂点を二度通らないものに限る) が存在するかどうかを判定し、そのようなパスの重みの最小値を求めよ…