グラフ
順列を題材とした面白い問題。トポロジカルソートの問題でもある。 問題へのリンク 問題概要 の順列であって、以下の 個の条件を満たすもののうち、辞書順最小のものを求めよ。 【 番目の条件】 は よりも先に来る 制約 考えたこと グラフの問題として考えて…
異常コーナーケース祭りのやばい問題だった 問題へのリンク 問題概要 頂点数 、辺数 の連結な単純無向グラフが与えられる。このグラフの頂点 にそれぞれ駒 が置いてある。次の操作を繰り返す。 駒 のうちの一方を選ぶ 選んだ駒を隣接する頂点のいずれかに動…
ICPC 本番に正解チームの現れなかった難問！ 問題へのリンク 問題概要 サイズのグリッドグラフから、いくつかの頂点と辺を削除してできる連結なグラフが与えられる。 このグラフの全域木であって、どの 2 つの葉も、その間の距離が偶数であるものを 1 つ求め…
二重頂点連結成分分解して得られる Block-Cut 木のクエリに答えていく問題。 問題へのリンク 問題概要 頂点数 、辺数 の連結な単純無向グラフが与えられる。次の 回のクエリに答えよ。 【クエリ】 各クエリでは 2 頂点 が与えられる。 個の頂点のうち、次の…
Block-Cut 木を試すのにすごくいい問題！ 問題へのリンク 問題概要 頂点数 、辺数 の連結な無向グラフが与えられる（単純とは限らない）。頂点 には、重み がついている。各頂点について、以下の問に答えよ。 【問】 その頂点を除外したグラフを考える。この…
すごく面白い問題だった！ 二重頂点連結成分分解からの Block-Cut 木ライブラリを試す目的で解いてみた。 問題へのリンク 問題概要 二次元平面上に 個の点がある。各点について、次の問に答えよ。 その点を除去した上で、各点に対応する頂点数 のグラフを考…
「グラフ」の基礎問題！ グラフを知らなくても解ける。 問題へのリンク 問題概要 個の都市 () があり、 本の道路がある。 番目の道路は、都市 と都市 を結んでいる。同じ 2 つの都市を結ぶ道路は、1 本とは限らない。 各都市から他の都市に向けて、何本の道…
面白い問題だった。 問題へのリンク 問題概要 下の図のような木を「ユ木」と呼ぶ（正式な定義は問題文参照）。 頂点数 の木が与えられ、いくつかの頂点を削除して「ユ木」にしたい。削除する頂点の個数の最小値を求めよ。 制約 考えたこと 与えられた木にお…
面白かった！ 一見 MST の問題に見えるけど、主客転倒すると Dijkstra だった。 問題へのリンク（仮） 問題概要 頂点数 、辺数 の連結な単純無向グラフが与えられる。頂点 には重み がついていて、辺 には重み がついている。このグラフの全域木のコストを次…
面白かった！ 解説 AC した！ 問題へのリンク 問題概要 頂点数 、辺数 の単純無向グラフが与えられる。このグラフの辺の順列であって、次の条件を満たすものを 1 つ求めよ（なければ -1 を出力せよ）。 【条件】 頂点数 、辺数 のグラフに対して、上記の順序…
evima さんの別解で解いた。 問題へのリンク 問題概要 頂点数 の単純な木が与えられる。この木に辺を 1 本追加して得られるグラフのうち、次の条件を満たすものの個数を求めよ。 単純グラフである サイクルをちょうど 1 つ含み、そのサイクルに含まれる頂点…
問題を言い換えるのが少し難しい 問題へのリンク 問題概要 頂点数 の木が与えられる（頂点番号 ）。 この木に対して「葉を 1 つ選んで削除する」という操作を繰り返す。頂点 1 を削除するまでの操作回数の最小値を求めよ。 制約 考えたこと 0-indexed で考え…
最初、頂点にアルファベット、辺に文字列を乗せたグラフを考えていたが、うまく解けなかった。 頂点に文字列を乗せて、しりとりが成立する箇所に辺を張ったグラフを考えるとうまくいった。 問題へのリンク 問題概要 英大文字 2 文字からなる 個の文字列 が与…
二部グラフ判定を書いたことがあれば、その要領で解ける！ 問題へのリンク 問題概要 頂点数 、辺数 の重み付き有向グラフが与えられる。各頂点 に値 を書き込む方法であって、どの辺 に対しても を満たすようなものを 1 つ求めよ (そのようなものが存在する…
グラフの基本問題！ 問題へのリンク 問題概要 の人 がいる。 組の友達関係があって、 組目の友達は人 と である。 人 1 の友達と、人 1 の友達の友達に相当する人 (人 1 を除く) が何人いるかを答えよ。 制約 解法 この問題はグラフの練習問題といえる。グラ…
Union-Find を上手に使おう！ 問題へのリンク 問題概要 初期状態では頂点数 、辺数 0 のグラフがある。頂点番号は である。次の 回のクエリに答えよ。 クエリタイプ 1：頂点 間に辺を張る クエリタイプ 2：頂点 を含む連結成分に含まれる頂点の番号にうち、 …
ちょっと実装が重たい。 問題へのリンク 問題概要 グリッドが与えられる。最初、どのマスにもなんらかの色（整数値）がついている。 マス から辺で接しているマスへの移動を繰り返し、マス と色が異なるマスに入ることなく移動できるマスの集まりを、マス の…
Euler Tour して、遅延評価セグ木（区間加算 + 区間 min）に乗せて......という解法を考えていたところに、あまりにもシンプルな想定解法を目にして、感動した！ 問題へのリンク 問題概要 頂点数 の重み付き木が与えられる。 に対して、次の問に答えよ。 個…
実はクエリごとに毎回愚直に Dijkstra 法を回しても間に合う！ 問題へのリンク 問題概要 最初、辺数 0 本、頂点数 個のグラフが与えられる。頂点番号は である。このグラフに対して 回のクエリが投げられる。 クエリタイプ 0：2 頂点 が指定されるので、頂点…
これ結構難しい気がする！ グラフの問題の一種。 問題へのリンク 問題概要 人 がいる。高橋君（ 人のいずれとも異なる）は、自分の秘密を、この中の人 に知られてしまった。 一般に、人 は新たに秘密を知ったときには、人 にも伝えてしまう。 高橋君の秘密は…
「グラフ」の基礎になるような、配列上のシミュレーションの問題。 問題へのリンク 問題概要 整数 が与えられる。 このとき、ボタンを押すと、画面の数値 () が に変わる。 最初の数値が 0 であるとき、ボタンを 3 回押すと、どんな数値に変わるか？ 考えた…
木の直径の問題！ 問題へのリンク 問題概要 頂点数 の木が与えられる。 番目の辺は、頂点 と頂点 を結んでおり、長さは である。 いずれかの街を出発し、道路による移動で全ての街を 1 度以上訪れるための移動距離の最小値を求めよ。 制約 考えたこと もし仮…
資源配分問題などとも呼ばれる、貪欲法が使える問題！ 問題へのリンク 過去によく似た類題を出題したことがある。 drken1215.hatenablog.com 問題概要 正の整数からなる長さ の数列 がある。頂点 をもつ木をすべて考えたときの、 の最小値を求めよ ( は頂点 …
いろんな解法あり。 問題へのリンク 問題概要 頂点数 の無向木が与えられる。各頂点 には色 が塗られている。 このグラフにおいて、 であるような頂点組 () についての、2 点 間の距離の総和を求めよ。 制約 考えたこと マージテクで考えた。例によって頂点 …
ChatGPT が問題文コピペのみで解けたと話題になった！ 問題へのリンク 問題概要 枚のカードがあり、表には 、裏には が書かれている。 先手と後手が交互にゲームする。交互にまだ残っているカードのうち、表の値が等しいか、裏の値が等しいような 2 枚のカー…
面白かった！！ 上手に変数変換することで「2 変数劣モジュラ関数の和の最小化」になるタイプの問題だった。 問題へのリンク 問題概要 考えたこと 一目見て、2 変数劣モジュラ関数の最小化 (燃やす埋める) っぽいと感じた。値が 500 以下というのも怪しい。 …
これは面白かった。 問題へのリンク 問題概要 の順列であって、以下の 個の条件を満たすものの個数を 998244353 で割った余りを求めよ。 について、 である 制約 考えたこと グラフの問題として考えることにした。つまり、0-indexed で表現すると 頂点数 、…
本当に色んな解法がある問題っぽい！！ 問題へのリンク 問題概要 頂点 の 頂点からなる無向グラフがあり、最初は辺がない。以下の 2 種類のオンラインクエリに答えよ。 クエリタイプ 1：頂点 間に辺を結ぶ クエリタイプ 2：頂点 の双方に隣接する頂点がある…
全方位木 DP の練習問題！！ が素数とは限らないので「左右から累積和」が必要なタイプの全方位木 DP。 問題へのリンク 問題概要 正の整数 と、頂点数 の木 が与えられる。この木の各頂点を「黒色」または「白色」に塗る。 各頂点 について、以下の条件をみ…
とても典型的で教育的な「燃やす埋める」の練習問題！ 問題へのリンク 問題概要 枚のカード があり、カード を使用するには だけコストがかかる。 一方、いくつかのカードを使用した場合、次の 種類のボーナス があり、ボーナス をクリアすると だけスコアを…
