木
木 DP シリーズ!!! 問題へのリンク 問題概要 区間グラフとは、 個の区間が与えられたときに、各区間を各頂点に対応させ、intersection がある区間同士に辺が張られたようなグラフのことである。 さて、 頂点の木が与えられる。この木の連結な部分グラフ (…
めちゃめちゃ簡単な実装で良いことがわかったので。 なんか、DFS 2 回か、全方位やるかなのかと思ってたけど、とても簡単な木DPで直径が求められることを知った。 問題へのリンク 問題概要 頂点の重み付き木が与えられるので、その直径の長さを求めよ。 制約…
マージテク童貞を卒業した!!! 問題へのリンク 問題概要 頂点の根付き木が与えられる (根の番号は 1)。また各頂点 には色 が塗られている。色は整数値で表される。各頂点 について、以下の問いに答えよ。 その頂点を根とした部分木を考える その部分木で「…
包除原理をとても素朴な状態で問いかける問題!!! 問題へのリンク 問題概要 頂点のツリーが与えられる。ツリーの各辺を白色または黒色に塗る 通りの方法のうち、以下の 個の制約をすべて満たすものの個数を求めよ。 個目の制約は 2 頂点 が指定され、 と …
面白かった!!! ツリーネタでまだこういうのが残ってるんだね!!! 問題へのリンク 問題概要 頂点の木が与えられる。 いま、木の頂点を 3 つ選ぶ (a, b, c とする)。このとき、 a と b を結ぶパスに含まれている辺集合 b と c を結ぶパスに含まれている辺…
面白かった!!!こういうのを確実に通せるようにならないと!!! 問題へのリンク 問題概要 頂点の木が与えられる。木の各辺を のラベルをつける方法のうち、 の値の最大値を求めよ。ただし は、2 頂点 を結ぶパスに含まれる辺の値の集合を考えたときに、そ…
実装に精彩を欠いてしまった...コンテスト中に WA を取りきれず... WA の原因は「すでに色を決めたはずの頂点について再度色を上書きしていることがある (現在見ている D 値について、それより小さい値の頂点とはつながっておらず、等しい D 値同士で結ばれ…
とにかく重たい... 問題へのリンク 問題概要 頂点のツリーが与えられる。各頂点には「白」か「黒」の色が塗られている。好きな頂点から開始して 今いる頂点の色を flip する 隣接する頂点を 1 つ選んで移動して、その頂点の色を flip する といういずれかの…
全方位木 DP の練習も兼ねて 問題へのリンク 問題概要 頂点数 のツリーが与えられる。ツリーの各頂点 に対して、 から出発して全頂点を訪れるまでに通る辺の本数の最小値を求めよ。 制約 解法 1: 全方位木 DP 1 つの根についての答えなら普通の木 DP で求め…
900 点なので備忘録程度に... 久しぶりに競プロでめちゃくちゃ楽しかった!!! 2 時間 10 分かかったので本番だったら通せていないけど、どうすればもっと早く解けたのかの反省もこめて。 問題へのリンク 問題概要 以下の条件を満たす 頂点の木を復元せよ。…
200 点となってるけど、他の 300 点と同じくらいに感じた! 頭の整理が大変だった...けど、面白い 問題へのリンク 問題概要 個の根付き木が与えられる。それぞれの木の頂点数は となっている。これらの木を使って、ゲームを行う。 最初、駒がスタート地点 (…
結構好き...だけど、完全既出だったらしい 問題へのリンク 問題概要 頂点 辺の連結な単純無向グラフが与えられる。各頂点 には重み が付いている。頂点 を始点としたウォークであって、ウォーク上のどの辺 に対してもその直後が ではない (直前に通った辺を…
木の走査って 根の方から情報を配っていく 子ノードたちの情報を引っ張ってくる (いわゆる木 DP) という二つの方向性があって、状況に応じてうまいこと使い分けるとよいイメージがある。 問題へのリンク 問題概要 頂点の木があたえられる。木の各頂点を 色に…
二乗の木 DP のいい練習問題!!!!! ついでに DP で最適化したい対象を入れ替えるタイプの問題でもある。そのようなタイプとして難しい問題としては、以下がある。 drken1215.hatenablog.com 問題へのリンク 問題概要 頂点の重みつきの根つき木が与えられ…
二乗の木 DP の例題として、すごくいい感じ!!! 問題へのリンク 問題概要 頂点のツリーが与えられて、各頂点 には 人がいる。いま、人を移動させて、各頂点の人数の最大値と最小値との差が 1 になるようにしたい。 1 人が辺 1 個分を移動するのに必要なコ…
すごく典型的な「二乗の木 DP」!!!!! そして包除原理との組み合わせ。 問題へのリンク 問題概要 を偶数とする。 頂点の木が与えられる。 頂点を 組の 2 つペアにする方法のうち、各ペアを結ぶパスをすべて考えたときに全辺が被覆されるようなものの個数…
最高に好きな問題 問題へのリンク 問題概要 頂点数 のツリー上でゲームを行う。高橋君は残った頂点から 1 つ選んで白く塗る。青木君は残った頂点から 1 つ選んで黒く塗る。 この操作をすべての頂点に色が塗られるまで繰り返したとき、黒く塗られたすべての頂…
とても教育的なツリーの探索問題。 問題へのリンク 問題概要 頂点の重み付き無向グラフが与えられる。このグラフの各頂点を白黒に塗る方法であって 同色に塗られた 2 頂点はどれを選んでも、その間のパスの長さは偶数である という条件を満たすものを求めよ…
これ大好き!!! 問題へのリンク 問題概要 頂点のツリーが与えられる。 初期状態ではすべての頂点に 1 枚ずつコインが乗っている。先手と後手が交互に コインが 1 枚以上乗っている頂点を 1 つ選び、その頂点のコインを取り除き その頂点以外の全頂点につい…
こどふぉらしい問題という感じかな。脈略のないような対象が継接ぎされた感じの問題 ^^; 問題へのリンク 問題概要 長さ の整合のとれたカッコ列全部を集めた集合についての trie 木を作る。 この trie 木上の最大マッチングのサイズを 1000000007 で割ったあ…
ツリーの問題!!!!!!!! 見るからにツリー DP っぽいのだけど、なかなかに頭が混乱する感じ。 この問題の心得は「最適解はどんな形をしているんだろう」を考えることかなと思う。それによって「こういうものだけ探索すれば良い」というのが見えて来る…
XOR について a ^ a = 0 な性質を上手く使う問題として。 問題へのリンク 問題概要 頂点の重み付きツリーが与えられる。 整数 が与えられ、ツリー上のパスであってパス上の重みの XOR 和が となるものが何個あるかを数えよ。 制約 考えたこと 根を 1 つ決め…
「TDPC うなぎ」の類題。 問題へのリンク 問題概要 頂点の重み付きツリーが与えられる。ツリー上の「頂点を共有しないようなパスの集合」として考えられるもののうち、パスの重みの総和の最大値を求めよ。 制約 考えたこと ツリー二重 DP をする。 ツリー DP…
一見、ツリー上のパスクエリ (オイラーツアーとかするやつ) な問題に見えるけど、そんなことはなかった 問題へのリンク 問題概要 頂点のツリー (辺に重み付き) が与えられる。ツリー上の 1 点 が与えられて、以下のクエリに 個答えよ: クエリ (): から を経…
ゆかたゆさんと一緒に解いた。 今後まだ解いてない様々な 500 点問題について何がポイントになっているのかをブログ書きながら明らかにして行きたい。500 点問題の苦手意識を克服する! 問題へのリンク 問題概要 二次元平面上に 個の点が与えられる。これら…
二乗の木DPの問題にようやく出会えました! 問題へのリンク 問題概要 頂点のツリーがあって、各頂点には値 が割り振られている。今ツリーのエッジを何本か取り除いて何個かの連結成分に分けたとき 連結成分内に含まれる全ノードの頂点の重みの和が負の値 連…
またしても、最後の最後がよく詰めきれず... (でもその最後のところの詰めの大変さが、この難易度帯の特徴なんだよね) 問題へのリンク 問題概要 頂点のツリーが与えられる。根ノードの番号を 1 とする。各ノード について、以下のクエリに答えよ: 初期状態を…
「交換しても悪化しない」というのは Greedy の証明の共通構造だとは思う。 問題へのリンク 問題概要 個の正の整数 がある。 これらの 個の整数に対応する 頂点のグラフを考えて、和が の形で表せる 2 数間に辺を引く。 このグラフの最大マッチングを求めよ…
取り急ぎ... 問題へのリンク 問題概要 N 頂点からなるツリーがあって、各辺で切ってできる連結成分のサイズとしてありうるものすべて集めたものが指定される。そのようなツリーを 1 つ構築せよ。存在しない場合は -1 とせよ 解法 とりあえず、 サイズ 1 は絶…
こういう系の問題、なかなか提出が怖くなるやつ。こういうのは背水の陣状態じゃないと躊躇してしまいそう... 問題へのリンク 問題概要 頂点数 、辺数 の有向グラフが与えられる。 どの頂点から出る辺数も 1 どの頂点から出発しても必ずノード 1 (root) にた…