けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

AtCoder ABC 138 D - Ki (400 点)

まさに「the 緑 diff」な問題だと思う。 「木を上手く扱えるか」を問いかける問題。 問題へのリンク 問題概要 頂点の木が与えられる。この木の頂点 1 を根とした根付き木を考える。各頂点には初期状態では 0 という数値が書かれている。以下の 回の操作を行…

AtCoder ABC 146 D - Coloring Edges on Tree (400 点)

軽めの構築問題!! 今回は「最大次数」というのが割と明らかだけど、しっかり構築法踏まえて証明する練習をすると、高難易度問題にも繋がりそう! 問題へのリンク 問題概要 頂点の木が与えられる。 本の辺に色を塗っていきたい。ただし、どの頂点についても…

Educational Codeforces Round 83 G. Autocompletion

頑張って DFS だけで通した!!! 問題へのリンク 問題概要 頂点数 の Trie 木と、そのうちの 個の頂点集合 が与えられる。 の各頂点 について、トライ木の根から出発して、以下の操作によって到達するまでの最小コストを求めよ。 トライ木の辺を 1 本先に進…

フォルシアゆるふわ競プロオンサイト #3 C - Bananas Multiplier (Hard) locked

ツリー上のパスクエリについての教育的典型題だった 問題へのリンク 問題概要 (意訳) 頂点の重み付きツリーが与えられる。以下の 個のクエリに答えよ。 各クエリは 2 頂点 , と値 が指定され、ツリー上の と とを結ぶパス上の辺の重みの積を求め、それと を…

Codeforces Round #617 (Div. 3) F. Berland Beauty

面白かった!!! 問題へのリンク 問題概要 頂点の木が与えられる。木の各辺に対して、以下の条件を満たすように 1 以上 1000000 以下の整数値を割り振りたい。 条件は 個ある 番目の条件は、2 頂点 と整数値 が指定されて、 を結ぶパス上の辺の値の最小値が…

Educational Codeforces Round 74 F. The Maximum Subtree (R2300)

木 DP シリーズ!!! 問題へのリンク 問題概要 区間グラフとは、 個の区間が与えられたときに、各区間を各頂点に対応させ、intersection がある区間同士に辺が張られたようなグラフのことである。 さて、 頂点の木が与えられる。この木の連結な部分グラフ (…

木の直径 (AOJ Course GRL_5_A)

めちゃめちゃ簡単な実装で良いことがわかったので。 なんか、DFS 2 回か、全方位やるかなのかと思ってたけど、とても簡単な木DPで直径が求められることを知った。 問題へのリンク 問題概要 頂点の重み付き木が与えられるので、その直径の長さを求めよ。 制約…

Educational Codeforces Round 2 E. Lomsat gelral (R2300)

マージテク童貞を卒業した!!! 問題へのリンク 問題概要 頂点の根付き木が与えられる (根の番号は 1)。また各頂点 には色 が塗られている。色は整数値で表される。各頂点 について、以下の問いに答えよ。 その頂点を根とした部分木を考える その部分木で「…

AtCoder ABC 152 F - Tree and Constraints (600 点)

包除原理をとても素朴な状態で問いかける問題!!! 問題へのリンク 問題概要 頂点のツリーが与えられる。ツリーの各辺を白色または黒色に塗る 通りの方法のうち、以下の 個の制約をすべて満たすものの個数を求めよ。 個目の制約は 2 頂点 が指定され、 と …

Codeforces Round #615 (Div. 3) F. Three Paths on a Tree

面白かった!!! ツリーネタでまだこういうのが残ってるんだね!!! 問題へのリンク 問題概要 頂点の木が与えられる。 いま、木の頂点を 3 つ選ぶ (a, b, c とする)。このとき、 a と b を結ぶパスに含まれている辺集合 b と c を結ぶパスに含まれている辺…

Codeforces Round #614 (Div. 1) C. Xenon's Attack on the Gangs (R2300)

面白かった!!!こういうのを確実に通せるようにならないと!!! 問題へのリンク 問題概要 頂点の木が与えられる。木の各辺を のラベルをつける方法のうち、 の値の最大値を求めよ。ただし は、2 頂点 を結ぶパスに含まれる辺の値の集合を考えたときに、そ…

キーエンス プログラミング コンテスト 2020 E - Bichromization (900 点)

実装に精彩を欠いてしまった...コンテスト中に WA を取りきれず... WA の原因は「すでに色を決めたはずの頂点について再度色を上書きしていることがある (現在見ている D 値について、それより小さい値の頂点とはつながっておらず、等しい D 値同士で結ばれ…

AtCoder ARC 097 F - Monochrome Cat (800 点)

とにかく重たい... 問題へのリンク 問題概要 頂点のツリーが与えられる。各頂点には「白」か「黒」の色が塗られている。好きな頂点から開始して 今いる頂点の色を flip する 隣接する頂点を 1 つ選んで移動して、その頂点の色を flip する といういずれかの…

AOJ 1595 Traffic Tree (AUPC 2016 day2-I)

全方位木 DP の練習も兼ねて 問題へのリンク 問題概要 頂点数 のツリーが与えられる。ツリーの各頂点 に対して、 から出発して全頂点を訪れるまでに通る辺の本数の最小値を求めよ。 制約 解法 1: 全方位木 DP 1 つの根についての答えなら普通の木 DP で求め…

AtCoder ARC 103 F - Distance Sums (900 点)

900 点なので備忘録程度に... 久しぶりに競プロでめちゃくちゃ楽しかった!!! 2 時間 10 分かかったので本番だったら通せていないけど、どうすればもっと早く解けたのかの反省もこめて。 問題へのリンク 問題概要 以下の条件を満たす 頂点の木を復元せよ。…

KUPC 2019 E - 根付き森二人用ゲーム

200 点となってるけど、他の 300 点と同じくらいに感じた! 頭の整理が大変だった...けど、面白い 問題へのリンク 問題概要 個の根付き木が与えられる。それぞれの木の頂点数は となっている。これらの木を使って、ゲームを行う。 最初、駒がスタート地点 (…

Codeforces Round #586 E. Tourism (R2200)

結構好き...だけど、完全既出だったらしい 問題へのリンク 問題概要 頂点 辺の連結な単純無向グラフが与えられる。各頂点 には重み が付いている。頂点 を始点としたウォークであって、ウォーク上のどの辺 に対してもその直後が ではない (直前に通った辺を…

AtCoder ABC 133 E - Virus Tree 2 (500 点)

木の走査って 根の方から情報を配っていく 子ノードたちの情報を引っ張ってくる (いわゆる木 DP) という二つの方向性があって、状況に応じてうまいこと使い分けるとよいイメージがある。 問題へのリンク 問題概要 頂点の木があたえられる。木の各頂点を 色に…

CPSCO 2019 session2 E - Mogu Mogu Gummi (600 点)

二乗の木 DP のいい練習問題!!!!! ついでに DP で最適化したい対象を入れ替えるタイプの問題でもある。そのようなタイプとして難しい問題としては、以下がある。 drken1215.hatenablog.com 問題へのリンク 問題概要 頂点の重みつきの根つき木が与えられ…

AOJ 3048 Averaging (AUPC 2018 day2-J)

二乗の木 DP の例題として、すごくいい感じ!!! 問題へのリンク 問題概要 頂点のツリーが与えられて、各頂点 には 人がいる。いま、人を移動させて、各頂点の人数の最大値と最小値との差が 1 になるようにしたい。 1 人が辺 1 個分を移動するのに必要なコ…

AtCoder ARC 101 E - Ribbons on Tree (900 点)

すごく典型的な「二乗の木 DP」!!!!! そして包除原理との組み合わせ。 問題へのリンク 問題概要 を偶数とする。 頂点の木が与えられる。 頂点を 組の 2 つペアにする方法のうち、各ペアを結ぶパスをすべて考えたときに全辺が被覆されるようなものの個数…

AtCoder AGC 014 D - Black and White Tree (900 点)

最高に好きな問題 問題へのリンク 問題概要 頂点数 のツリー上でゲームを行う。高橋君は残った頂点から 1 つ選んで白く塗る。青木君は残った頂点から 1 つ選んで黒く塗る。 この操作をすべての頂点に色が塗られるまで繰り返したとき、黒く塗られたすべての頂…

AtCoder ABC 126 D - Even Relation (400 点)

とても教育的なツリーの探索問題。 問題へのリンク 問題概要 頂点の重み付き無向グラフが与えられる。このグラフの各頂点を白黒に塗る方法であって 同色に塗られた 2 頂点はどれを選んでも、その間のパスの長さは偶数である という条件を満たすものを求めよ…

AtCoder AGC 033 C - Removing Coins (800 点)

これ大好き!!! 問題へのリンク 問題概要 頂点のツリーが与えられる。 初期状態ではすべての頂点に 1 枚ずつコインが乗っている。先手と後手が交互に コインが 1 枚以上乗っている頂点を 1 つ選び、その頂点のコインを取り除き その頂点以外の全頂点につい…

Codeforces 554 DIV2 D. Neko and Aki's Prank (R2000)

こどふぉらしい問題という感じかな。脈略のないような対象が継接ぎされた感じの問題 ^^; 問題へのリンク 問題概要 長さ の整合のとれたカッコ列全部を集めた集合についての trie 木を作る。 この trie 木上の最大マッチングのサイズを 1000000007 で割ったあ…

AtCoder AGC 001 C - Shorten Diameter (600 点)

ツリーの問題!!!!!!!! 見るからにツリー DP っぽいのだけど、なかなかに頭が混乱する感じ。 この問題の心得は「最適解はどんな形をしているんだろう」を考えることかなと思う。それによって「こういうものだけ探索すれば良い」というのが見えて来る…

AtCoder ARC 045 C - エックスオア多橋君

XOR について a ^ a = 0 な性質を上手く使う問題として。 問題へのリンク 問題概要 頂点の重み付きツリーが与えられる。整数 が与えられ、ツリー上のパスであってパス上の重みの XOR 和が となるものが何個あるかを数えよ。 制約 考えたこと 根を 1 つ決めて…

CS Academy FII Code #1 D - Sugarel in Love

「TDPC うなぎ」の類題。 問題へのリンク 問題概要 頂点の重み付きツリーが与えられる。ツリー上の「頂点を共有しないようなパスの集合」として考えられるもののうち、パスの重みの総和の最大値を求めよ。 制約 考えたこと ツリー二重 DP をする。 ツリー DP…

AtCoder ABC 070 D - Transit Tree Path (400 点)

一見、ツリー上のパスクエリ (オイラーツアーとかするやつ) な問題に見えるけど、そんなことはなかった 問題へのリンク 問題概要 頂点のツリー (辺に重み付き) が与えられる。ツリー上の 1 点 が与えられて、以下のクエリに 個答えよ: クエリ (): から を経…

AtCoder ARC 076 D - Built? (500 点)

ゆかたゆたんと一緒に解いたん。 今後まだ解いてない様々な 500 点問題について何がポイントになっているのかをブログ書きながら明らかにして行きたい。500 点問題の苦手意識を克服するぞい。 問題へのリンク 問題概要 二次元平面上に 個の点が与えられる。…