evima さんの別解で解いた。 問題へのリンク 問題概要 頂点数 の単純な木が与えられる。この木に辺を 1 本追加して得られるグラフのうち、次の条件を満たすものの個数を求めよ。 単純グラフである サイクルをちょうど 1 つ含み、そのサイクルに含まれる頂点…

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

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

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

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

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

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

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

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

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

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

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

面白かった 問題へのリンク 問題概要 頂点 辺の森が与えられる。各頂点 には、値 が付いている。これにいくつかの辺を追加して、連結にしたい。 頂点 と頂点 とを結ぶのに必要なコストは である すでに辺がある二頂点間は結べない 一度辺を張るのに使用した…

とても教育的な Union-Find！！！ 問題へのリンク 問題概要 人がいて、 組の友達関係と、 組のブロック関係がある (いずれも双方向的)。 各人について、 直接的な友達関係ではない ブロック関係でもない 友達の友達の...とたどっていくと到着できる ような人…

800 点埋めをしていく！！！ 問題見て、コーナーケース怖い系かな...と思ったけど、ちゃんと一発で通せてよかった 問題へのリンク 問題概要 行 列のマス目があって、以下の条件を満たすように各マスに整数値を書き込みたい (整数値を とする): どのマスの数…

なんか既視感があった。それがどこから来たのか、いまだよくわからない。。。 問題へのリンク あと、今回のような二部グラフの作り方はあり本 P.205 の POJ 3041 Asteroids あたりもそんな感じ。こういうのを一度見ておくと、この二部グラフ作りは定石になる…

これがこのセットで一番難しかった。 こういうのをグラフで考えるのは典型と言えば典型か。 問題へのリンク 問題概要 組の整数組 がある。それぞれの組から整数を選んだ 種類の整数に含まれる整数の種類数の最大値を求めよ。 制約 考えたこと 数値をノードに…

これまた Union-Find を用いる教育的問題！！！！！ 問題へのリンク 問題概要 枚のカードがあって、それぞれ 1 か 2 の数値が書かれている。 枚のカードの数値 をすべて当てたい。 現在、以下の形式をした条件が 個与えらている: 整数 に対して、 は偶数であ…

DP とかメモ化再帰とか考え出すとドツボにはまる...素直な考察が大事だね。 問題へのリンク 問題概要 のグリッドが与えられる。各マスは白か黒で塗られている。「黒」マスと「白」マスのペアであって、 黒マスから出発して、隣接するマスを辿っていくことで…