面白かった 問題へのリンク 問題概要 のグリッドがある。各マスには数値が書かれている。 個の数値を集めると、 が 個ずつある。 今、各行について、その 個の数値を自由に並び替えていく。 その結果として、すべての列が の順列であるようにすることが可能…

また 1 つ、MST 系の問題のストックが増えた。でも実質的には整数問題だった。 問題へのリンク 問題概要 頂点数 、辺数 のグラフがある。このグラフに以下の操作 を実施することで重み付き無向グラフを作る。 に対して、頂点 と頂点 % の間に、重み の辺を張…

lca の問題リストに追加！ 問題へのリンク 問題概要 頂点数 の木と、2 頂点 が与えられる。各 に対して、以下の問いに答えよ。 パス - と、パス - の両方に含まれる頂点の個数を答えよ 制約 考えたこと 頂点 を始点とする根付き木を作った。そうしたら、あと…

想定解法が天才的に思えたとしても、愚直なグラフ探索でも解ける！ 時には腕力で頑張るのも有効！ 問題へのリンク 問題概要 競技プログラマ がいる。 組については、どちらが強いかが分かっている。具体的には に対して は、 より強い ということが分かって…

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

壁にぶつかるまで動く設定の迷路問題！ 問題へのリンク 問題概要 のグリッドがある。各マスは壁 (文字 '#') か通路 (文字 '.') かのいずれかである。グリッドの外周のマスはすべて壁であることが保証されている。 プレイヤーは最初、マス にいる (0-indexed)…

Functional グラフのサイクル検出問題！ 問題へのリンク 問題概要 頂点数 のグラフが与えられる。頂点 からは頂点 への辺が接続していて、辺数は全部で 本ある。 このグラフにおいて、同一頂点を複数回含まない有向サイクルをひとつ求めてください。具体的に…

再帰関数を使った全探索が書けるかどうかが試される！ 問題へのリンク 問題概要 人のスポーツ選手を 個のグループに分けたい。 ただし、仲の悪いスポーツ選手の組が 組ある。任意の に対して、選手 と選手 を同じグループに属させてはならない。 この制約を…

セグ木上二分探索使ったというコメントをよく見たけど、僕の方針でも使うことになった 問題へのリンク 問題概要 頂点数 、辺数 の単純な重み付き無向グラフが与えられる。 日目、 個の頂点 がウィルスに感染した。一度ウィルスに感染した頂点はずっと感染し…

DFS をちゃんと分かっているかが問われる！ DFS の動きをシミュレートする問題 問題へのリンク 問題概要 この問題はインタラクティブ問題である。 頂点数 、辺数 の連結かつ単純な無向グラフがある。ただし最初の入力として与えられるのは の値のみである。 …

人生で初めて解くとよいグラフの問題という感じ！ 問題へのリンク 問題概要 頂点数 、辺数 の単純な無向グラフが与えられます。 番目の辺は、頂点 と頂点 を結んでいます。 各頂点 に対して、頂点 に隣接する頂点を小さい順に出力してください。 制約 解法 …

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

人生で最初に解きたい BFS の問題！ 問題へのリンク 問題概要 のグリッドが与えられます。各マスは壁 (文字 '#')、通路 (文字 '.') のいずれかです。通路マスに入ることはできますが、壁マスに入ることはできません。 スタートマス (入力で与えられる) から…

MST の理解が問われる面白い教育的問題！ 問題へのリンク 問題概要 頂点数 、辺数 の連結な重み付き単純無向グラフ が与えられる。なお、各辺の重みはすべて互いに異なることが保証されている。 の最小全域木を とする (一意に定まることが示せる)。 このグ…

「最適解の個数」を求めるという超典型！ 問題へのリンク 問題概要 頂点数 、辺数 の単純無向グラフが与えられます。 頂点 から頂点 へと至る最短経路の本数を 1000000007 で割った余りを答えてください。 制約 解法 最短路を求めるだけならば、BFS を使うこ…

下手を打つと密なグラフになって TLE してしまう！！ スーパーノードを作ることでグラフを sparse にするテク！ 問題へのリンク 問題概要 以上 以下の整数値からなる 個の有限集合 が与えられる。 以下の操作を最小回数繰り返すことによって、「 と をともに…

グラフの入門に！ 問題へのリンク 問題概要 頂点数 、辺数 の単純無向グラフが与えられます。 各頂点 に対して、「友達の友達」、つまり頂点 からの距離が 2 であるような頂点の個数を求めてください。 自分自身や、友達 (距離が 1 である頂点) は含めないも…

今の時代なら確実に灰色 diff ですね。 問題へのリンク 問題概要 頂点数 、辺数 の単純無向グラフが与えられる。 頂点 と頂点 とを結ぶ辺は存在しないことがわかっている。 ある頂点 から 2 本の辺を辿ることで頂点 に到達できるかどうかを判定せよ。 制約 …

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

木を探索する練習問題。頭を柔らかくするのが肝心。 問題へのリンク 問題概要 あなたはアメーバの観察記録をつけました。最初 匹のアメーバがおり、番号は です。 観察記録は時系列順に 個あり、 番目の観察記録は 番号 のアメーバが分裂して消滅し、 新たに…

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

「要素の削除」をする必要がある場合は set が使えたりする 問題へのリンク 問題概要 最初、頂点数 、辺数 のグラフがある。 このグラフに対して次の 個のクエリに答えて、毎クエリ後にその時点での「グラフの孤立点の個数」を出力せよ。 クエリタイプ 1 (1 …

DFS などの探索をしても解けるし、単に次数を見るだけでも解ける。 問題へのリンク 問題概要 個の葉をもつスターグラフを、レベル のスターと呼ぶことにする。 高橋君は、はじめ何個かのスターからなるグラフを持っている。これらのスターの頂点数の総和は …

これも Yosupo Judge の問題名でタイトル検索しても出てくるように。 問題へのリンク 問題概要 頂点 辺の無向グラフが与えられる。 番目の辺は頂点 を結ぶ。単純グラフとは限らない。 与えられたグラフにサイクルが含まれるならば、辺素かつ頂点素なサイクル…

Yosupo Judge の問題名でタイトル検索しても出てくるように。 問題へのリンク 問題概要 頂点 辺の有向グラフが与えられる。 番目の辺は頂点 を結ぶ。単純グラフとは限らないが、自己ループはない。 与えられたグラフにサイクルが含まれるならば、辺素なサイ…

私たちは、グラフアルゴリズムとして DFS や BFS を学ぶと 頂点 s から頂点 t へ辿り着けるかどうかを判定する 連結成分の個数を求める 二部グラフ判定する トポロジカルソートする などといった例題を次々とこなしていき、グラフ探索スキルを高めていく道を…

「ABC 301 E - Pac-Takahashi」の類題とも言うべき ICPC 系の問題！ 問題へのリンク (AOJ) 問題へのリンク (AtCoder) editorials 問題概要 頂点数 、辺数 の重み付き無向グラフが与えられる。頂点番号は とする。 番目の辺は頂点 を結んでおり、その重みは …

前処理して頂点数を減らしたグラフ上で TSP！！！ ICPC ではすごくよく見るパターンですね！ 問題へのリンク 問題概要 サイズのグリッドがある。各マスは 壁マス：'#' 通路マス：'.' お菓子マス：'o' (18 個以内であることが保証される) スタートマス：'S' …

重心分解！ 問題へのリンク 問題概要 (インタラクティブ) 頂点の木が与えられる。なお、この木はどの頂点の次数も 以下であることが保証されている。 A さんは、この木のいずれかの頂点 を考えている。その頂点 を当てるゲームを行う。 あなたは最大 14 回の…

まさに文字通り、強連結成分分解をしてください、という問題ですね。そしてこの問題は、Yosupo Judge の Strongly Connected Components が元になっているようです。 問題へのリンク 問題概要 頂点 辺の有向グラフが与えられる。 番目の辺は である。このグ…