連結成分
一般にグラフの問題を解くときは「連結成分ごとに解けば良いのではないか」と考えるのが有効なことがある！ その意識がしっかりしていれば、「グラフが非連結の場合に気づかなかった」という罠を回避できる！！ 問題へのリンク 問題概要 頂点数 、辺数 の単…
Union-Find を上手に使うと解けるいい練習問題ですね。 問題へのリンク 問題概要 個の都市があって、都市間を 本の「道路」と 本の「鉄道」が結んでいる。各道路と各鉄道は、結んでいる都市間を双方向に移動することができる。 各都市 に対して、以下の条件…
Union-Find や、DFS、BFS などで解ける問題ですね。 問題へのリンク 問題概要 頂点数 、辺数 の連結な単純無向グラフ が与えられます。 グラフ の辺 が橋であるとは、その辺を除去したときに、グラフが連結でなくなることを指すものとします。 グラフ におい…
今や Union-Find やるだけだと茶色 diff (下手したら灰色 diff) だけど、ちゃんと考察要素を入れるとやっぱり緑色 diff になるのね。 問題へのリンク 問題概要 正の整数からなる整数列 が与えられる。以下の操作を好きなだけ行うことによって、 個の値がすべ…
なんとか解けた。若干エスパー気味に解いた。 問題へのリンク 問題概要 頂点数 、辺数 の無向単純グラフが与えられる。 各 に対して、この誘導部分グラフ (頂点集合はそのまま、辺集合は部分集合) であって、次数が奇数の頂点が 個であるようなものの個数を …
無向グラフの連結成分の個数を数える問題 ジャッジへのリンク 問題へのリンク 問題概要 頂点数 、辺数 の無向グラフが与えられる。このグラフにいくつかの辺を新たに追加することによって、グラフ全体が連結となるようにしたい。 追加すべき辺の本数の最小値…
こどふぉのこの回、いい問題が多かった気がするので解き直し。最上位の桁から順に見ていって、0 と 1 とに分類していって...とするのはよく見る気がする！！！ 問題へのリンク 問題概要 どの要素も互いに相異なる非負整数列 が good であるとは、以下の条件…
条件反射で二分探索してしまった！！！この問題めっちゃ面白くて好き！！！ 問題へのリンク editorial 問題概要 平面上に 2 直線 で囲まれた通路がある。この通路の中の の部分に 本の大きさの無視できる釘が打たれており、 本目の釘の座標は である。 高橋…
問題へのリンク 問題概要 頂点数 、辺数 の無向グラフが与えられる。各頂点 には値 が書かれている。以下の操作を好きな順序で好きな回数だけ行うことで、各頂点 の数値が であるような状態にすることが可能かどうかを判定せよ。 辺 を選んで、以下のいずれ…
結構いろんな考え方のできる問題！ 問題へのリンク 問題概要 頂点数 、辺数 の無向グラフであって、次の条件を満たすものの個数を 1000000007 で割ったあまりを求めよ。 自己ループを持たない すべての頂点の次数が 2 以下である 各連結成分のサイズを並べた…
こないだの ARC でめっちゃ似た問題が出たので！これは、SolveMe を含む、りんごさんによる伝説のセット。 drken1215.hatenablog.com 問題へのリンク 問題概要 頂点数 のグラフが与えられる (入力は の隣接行列で与えられ、初期状態では非連結である)。この…
とてもシンプルな設定で面白かった！でもバグらせてそうで、提出するのは怖かった。 問題へのリンク 問題概要 頂点数 、辺数 の単純無向グラフが与えられる。初期状態では頂点 1 と頂点 は非連結である。 先手と後手が、交互に 1 本ずつ辺を追加していく。た…
Union-Find の典型的な問題！！ でも、DFS や BFS でも解くことができる。 問題へのリンク 問題概要 人 から 人 までの 人の人がいます。 「人 と人 は友達である」という情報が 個与えられます。同じ情報が複数回与えられることもあります。 と が友達、か…
Union-Find の練習問題という雰囲気ながら、DFS や BFS でも解ける 問題へのリンク 問題概要 頂点数 、辺数 の単純無向グラフが与えられる。これに最小本数の辺を追加することで全体が連結となるようにしたい。その最小本数を求めよ。 制約 考えたこと 全体…
えーーー、300 点！？ 問題へのリンク 問題概要 二次元平面上に 点が与えられる。これらの点の x 座標、y 座標を抽出すると、それらは の順列となっている。 各 に対して、点 から 自分よりも x 座標と y 座標がともに大きな点 自分よりも x 座標と y 座標が…
いわゆる区間分割する系の DP。こういう系は高速化を要求するタイプの問題が多いけど、今回は素直な二乗 DP で OK！ 問題へのリンク 問題概要 直線上にカツが 個ある。 個目のカツは位置 にあり、その重さは である。これらのカツを、次のようにしてすべて回…
こういう系すごく楽しいよね 問題へのリンク 問題概要 頂点数 、辺数 の重み付き有向単純グラフ が与えられる。 このグラフ上で次の条件を満たすパス (同じ頂点を二度通らないものに限る) が存在するかどうかを判定し、そのようなパスの重みの最小値を求めよ…
こういうの大好き！ 問題へのリンク 問題概要 の盤面 A が与えられる。各マスは白か黒かのいずれかである。次の条件を満たす、同じ大きさの白黒の二つの盤面の組 (S, T) を構築せよ S の黒マスはすべて縦横に連結である T の黒マスはすべて縦横に連結である …
面白かった 問題へのリンク 問題概要 頂点 辺の森が与えられる。各頂点 には、値 が付いている。これにいくつかの辺を追加して、連結にしたい。 頂点 と頂点 とを結ぶのに必要なコストは である すでに辺がある二頂点間は結べない 一度辺を張るのに使用した…
頭がゴチャゴチャしてきて、詰め切るのがとても大変だった。 でも整理し切った後に出てくる性質は、至極単純なものだった。面白い。 問題へのリンク 問題概要 のグリッドが与えられ、各マスは白黒に塗られている。この盤面をレベル 1 のフラクタルとする。 …
微妙なコーナーケースに注意 問題へのリンク 問題概要 の書かれたカードがそれぞれ 枚ある。以下の条件を満たすようにペアリングしていくとき、最大で何組できるか？ ペアとなるカードの数値の差は 1 以下 制約 考えたこと 一瞬、 値が等しいペアを作れるだ…
とても教育的な Union-Find！！！ 問題へのリンク 問題概要 人がいて、 組の友達関係と、 組のブロック関係がある (いずれも双方向的)。 各人について、 直接的な友達関係ではない ブロック関係でもない 友達の友達の...とたどっていくと到着できる ような人…
800 点埋めをしていく！！！ 問題見て、コーナーケース怖い系かな...と思ったけど、ちゃんと一発で通せてよかった 問題へのリンク 問題概要 行 列のマス目があって、以下の条件を満たすように各マスに整数値を書き込みたい (整数値を とする): どのマスの数…
めるアイコン変換すると良さそうなのはすぐに思い至った。そこから繋げられずに editorial を見た。 問題へのリンク 問題概要 二次元平面上に 個の点がある。このうちの 2 点 が指定されている。その 2 点間のマンハッタン距離を とする。 この 点について「…
確かに、ついこの間の ABC 131 F の類題だね 問題へのリンク 問題概要 のグリッドがあって、 マス分が黒く塗られている 長方形の三頂点状に並んだ黒マスの組を選んで、残りの頂点に相当する位置を黒く塗る (コスト 0) 黒くないマスを一つ選んで黒く塗る (コ…
なんか既視感があった。それがどこから来たのか、いまだよくわからない。。。 問題へのリンク あと、今回のような二部グラフの作り方はあり本 P.205 の POJ 3041 Asteroids あたりもそんな感じ。こういうのを一度見ておくと、この二部グラフ作りは定石になる…
これがこのセットで一番難しかった。 こういうのをグラフで考えるのは典型と言えば典型か。 問題へのリンク 問題概要 組の整数組 がある。それぞれの組から整数を選んだ 種類の整数に含まれる整数の種類数の最大値を求めよ。 制約 考えたこと 数値をノードに…
これまた Union-Find を用いる教育的問題！！！！！ 問題へのリンク 問題概要 枚のカードがあって、それぞれ 1 か 2 の数値が書かれている。 枚のカードの数値 をすべて当てたい。 現在、以下の形式をした条件が 個与えらている: 整数 に対して、 は偶数であ…
面白かった。 「全体についての総和についての総和」を「個別の要素についての総和を各要素について総和」とするテク 区間の連結成分の個数は、各隙間に左端が入り込むかを数える という典型テクが詰まった問題。 問題へのリンク 問題概要 要素からなる数列 …
とても教育的な問題ですね。 UnionFind 木の基本的な使い方 (連結成分のサイズ獲得含む) クエリを先読みしておいて逆順に処理 (多くのクエリ先読み問題ではもっと変な順番で処理したりする) 差分のみ更新する考え方 といったあたりを学ぶことができる。 問題…
