マージテク
Union-Find を上手に使おう! 問題へのリンク 問題概要 初期状態では頂点数 、辺数 0 のグラフがある。頂点番号は である。次の 回のクエリに答えよ。 クエリタイプ 1:頂点 間に辺を張る クエリタイプ 2:頂点 を含む連結成分に含まれる頂点の番号にうち、 …
いろんな解法あり。 問題へのリンク 問題概要 頂点数 の無向木が与えられる。各頂点 には色 が塗られている。 このグラフにおいて、 であるような頂点組 () についての、2 点 間の距離の総和を求めよ。 制約 考えたこと マージテクで考えた。例によって頂点 …
本当に色んな解法がある問題っぽい!! 問題へのリンク 問題概要 頂点 の 頂点からなる無向グラフがあり、最初は辺がない。以下の 2 種類のオンラインクエリに答えよ。 クエリタイプ 1:頂点 間に辺を結ぶ クエリタイプ 2:頂点 の双方に隣接する頂点がある…
重み付き Union-Find そのもの。もしくは、列挙可能 Union-Find 使ってマージテクでも。 問題へのリンク 問題概要 個の整数値 に関する制約条件が 個与えられる。 番目の制約条件では 3 つの整数の組 が与えられ、 という形をしている。ここで、次のクエリに…
めっちゃ面白い問題だった! 問題へのリンク 問題概要 頂点 0 を根とする頂点数 の根付き木が与えられます。頂点 0 以外の頂点 には数値 が書かれています。今、頂点 0 にコマが置いてあります。 高橋くんと青木くんが次の動作を交互に繰り返します。 青木く…
マージテクを知らなくても雰囲気で通せるのかもしれない 問題へのリンク 問題概要 人の生徒がそれぞれクラス に所属している。 各生徒はそれぞれの家から出発したあと、他の生徒と合流を繰り返しながら学校へ向かう。一度合流した生徒が分かれることはない。…
こういうのは包除原理しかない! 問題へのリンク 問題概要 人の人がいる。 人 の身長は である。以下の条件を満たすように、 組のペアを作る方法は何通りあるか、998,244,353 で割ったあまりを求めよ。 どの人もちょうど一つのペアに含まれる。 どのペアも、…
確かに、えでゅふぉのラス問にありそう! 問題へのリンク 問題概要 人の選手が距離 のレースを走る。 人目はデフォルトでは距離 1 走るのに 秒かかる。 スタートから距離が のところにアイテムがある。各アイテムは各選手に対して独立に、確率 で減速 (距離 …
マージテク童貞を卒業した!!! 問題へのリンク 問題概要 頂点の根付き木が与えられる (根の番号は 1)。また各頂点 には色 が塗られている。色は整数値で表される。各頂点 について、以下の問いに答えよ。 その頂点を根とした部分木を考える その部分木で「…
たくさんの方法がとれる超教育的な問題なので、たくさんの方法で解いてみた! 問題へのリンク 問題概要 の 個の集合がある。 と とを併合する という操作が 回行われた。以下の 個のクエリに答えよ: と が何回目の操作後にはじめて一緒のグループになったか…