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

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

AtCoder ABC 359 F - Tree Degree Optimization (2D, 青色, 550 点)

資源配分問題などとも呼ばれる、貪欲法が使える問題! 問題へのリンク 過去によく似た類題を出題したことがある。 drken1215.hatenablog.com 問題概要 正の整数からなる長さ の数列 がある。頂点 をもつ木をすべて考えたときの、 の最小値を求めよ ( は頂点 …

AtCoder ABC 359 G - Sum of Tree Distance (3D, 黄色, 600 点)

いろんな解法あり。 問題へのリンク 問題概要 頂点数 の無向木が与えられる。各頂点 には色 が塗られている。 このグラフにおいて、 であるような頂点組 () についての、2 点 間の距離の総和を求めよ。 制約 考えたこと マージテクで考えた。例によって頂点 …

AtCoder ABC 350 G - Mediator (3D, 黄色, 600 点)

本当に色んな解法がある問題っぽい!! 問題へのリンク 問題概要 頂点 の 頂点からなる無向グラフがあり、最初は辺がない。以下の 2 種類のオンラインクエリに答えよ。 クエリタイプ 1:頂点 間に辺を結ぶ クエリタイプ 2:頂点 の双方に隣接する頂点がある…

EDPC (Educational DP Contest) V - Subtree (2D)

全方位木 DP の練習問題!! が素数とは限らないので「左右から累積和」が必要なタイプの全方位木 DP。 問題へのリンク 問題概要 正の整数 と、頂点数 の木 が与えられる。この木の各頂点を「黒色」または「白色」に塗る。 各頂点 について、以下の条件をみ…

AtCoder ARC 171 C - Swap on Tree (黄色, 600 点)

備忘録として。解説よりもおそらく面倒な DP をした。 問題へのリンク 問題概要 考えたこと 基本的に木 DP のノリで考えることにした。 根を 1 つとったとき、異なる部分木間で交換される頂点はただだか 1 個以内である。そこで次の DP をした。 dp[v][k] ← …

AtCoder AGC 005 F - Many Easy Problems (銅色, 1900 点)

Polynomial Taylor Shift が使えた! 問題へのリンク 問題概要 頂点数 の木が与えられる。各 に対して、次の問いに答えよ。 頂点から 個の頂点を選ぶ 通りの方法それぞれについて その 個の頂点をすべて含む連結な部分グラフのサイズとして考えられる最小値…

CodeQUEEN 2023 決勝 C - Path Intersection

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

AtCoder ABC 302 Ex - Ball Collector (橙色, 625 点)

undo 付き Union-Find! 問題へのリンク 問題概要 頂点数 の木が与えられる。各頂点には、数値 の書かれたボールと、数値 の書かれたボールがある。 各 に対して、次の問に答えよ。 パス - 上の各頂点から ボールを 1 個ずつ選んだときの ボールに書かれた数…

AtCoder ABC 274 C - Ameba (灰色, 300 点)

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

AtCoder ABC 303 E - A Gift From the Stars (緑色, 475 点)

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

第4回 ドワンゴからの挑戦状 予選 2018 E - ニワンゴくんの家探し (1000 点)

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

AtCoder ABC 259 F - Select Edges (青色, 500 点)

木 DP のいい感じの練習問題だった! 問題へのリンク 問題概要 頂点数 の重み付き木が与えられる (重みは負のこともある)。 この木の辺の部分集合であって、各頂点 に接続する辺の本数が 本以下であるようなものに対して、辺の重みの総和の最大値を求めよ。 …

AtCoder ABC 246 G - Game on Tree 3 (黄色, 600 点)

めっちゃ面白い問題だった! 問題へのリンク 問題概要 頂点 0 を根とする頂点数 の根付き木が与えられます。頂点 0 以外の頂点 には数値 が書かれています。今、頂点 0 にコマが置いてあります。 高橋くんと青木くんが次の動作を交互に繰り返します。 青木く…

AtCoder ABC 213 D - Takahashi Tour (茶色, 400 点)

DFS (深さ優先探索) の動きをシミュレーションする問題。 問題へのリンク 問題概要 頂点番号が であるような木が与えられます。 今このグラフにおいて、頂点 1 から出発して、次の動きを繰り返します。 いまいる頂点に隣接する頂点のうち、まだ訪れたことが…

yukicoder No.763 Noelちゃんと木遊び

いわゆる「木上の最大安定集合問題」です! 超典型問題です。 問題へのリンク 問題概要 頂点数 の木が与えられます。木からいくつかの頂点を選んで削除します。その結果、木はいくつかの連結成分に分かれます。 分かれた連結成分の個数の最大値を求めてくだ…

AtCoder ABC 014 D - 閉路 (試験管青色)

木上のパスに関する問題!! LCA で解決できる典型問題 問題へのリンク 問題概要 頂点数 の木が与えられる。次の 個のクエリに答えよ。 各クエリでは木上の 2 頂点 が与えられる 木に辺 を仮に追加したとすると、閉路が 1 個形成される その閉路に含まれる辺…

AtCoder ABC 019 D - 高橋くんと木の直径 (試験管水色)

木の直径の求め方を知っていれば解ける!! 問題へのリンク 問題概要 頂点数 の木があるが、その形状についての情報はあらかじめわからない。あなたの目的は、この木の直径の長さを求めることである。 そのために、以下のクエリを 100 回まで投げることがで…

AtCoder ARC 115 D - Odd Degree (黄色, 600 点)

なんとか解けた。若干エスパー気味に解いた。 問題へのリンク 問題概要 頂点数 、辺数 の無向単純グラフが与えられる。 各 に対して、この誘導部分グラフ (頂点集合はそのまま、辺集合は部分集合) であって、次数が奇数の頂点が 個であるようなものの個数を …

JOI 本選 2007 E - 最軽量のモビール (AOJ 0520, 難易度 7)

読解が大変だけど、本質的には木 DP な問題 ジャッジへのリンク AOJ ページ 問題概要 本の棒を用いて、下図のようなモビールを作りたい。 入力としては、各棒 についての 左端から支点までの長さ 右端から支点までの長さ 左端からつながっている棒の index (…

AtCoder ABC 187 E - Through Path (水色, 500 点)

これの応用問題って感じだった!! drken1215.hatenablog.com 問題へのリンク 問題概要 頂点数 の木が与えられる。 番目の辺は頂点 と頂点 とを結んでいる。はじめ、各頂点には、値 0 が書き込まれている。以下の 個のクエリを処理したあとの、各頂点に書き…

Codeforces Round #683 (Div. 1) C. Xor Tree (R2100)

こどふぉのこの回、いい問題が多かった気がするので解き直し。最上位の桁から順に見ていって、0 と 1 とに分類していって...とするのはよく見る気がする!!! 問題へのリンク 問題概要 どの要素も互いに相異なる非負整数列 が good であるとは、以下の条件…

Codeforces Round #681 (Div. 1) E. Black, White and Grey Tree (R3000)

最初まんまと罠にひっかかった 問題へのリンク 問題概要 頂点数 の木が与えられる。各頂点には 0, 1, 2 のいずれかの色 (0: 灰色, 1: 白色, 2: 黒色) が割り振られている。以下の操作を最小回数行うことで、木を消滅させたい。最小回数を求めよ。 [操作]:残…

CPSCO2019 Session4 F - Lost Tree (800 点設定)

テスターしてました!難しかった。 問題へのリンク 問題概要 ラスク君は木を持っていましたが、なくしてしまいました。 この木は、頂点に 1 以上頂点数以下の相異なる整数の番号がついていて、各辺には 以上 以下の整数の重みが定まっていました。 頂点数は …

AtCoder ARC 106 F - Figures (橙色, 800 点)

コンテスト本番、こっちをやればよかった...ところで解説が天才すぎる! 問題へのリンク editorial 問題概要 個の部品と、 個の接続用部品とがある。これらを用いてフィギュアを作ろうとしている。 番目の部品には 個の穴がついている。接続用部品は、2 個の…

AOJ 2677 Breadth-First Search by Foxpower (JAG 春コン 2014 A) (400 点)

LCA ライブラリを持っていれば書くだけ! 問題へのリンク editorial 問題概要 頂点の根付き木が与えられる (根は頂点 0)。この木上で幅優先探索を行う (隣接する頂点のうち、頂点番号が小さい順にキューに push する)。 このとき、探索順序が であったとした…

Codeforces Round #250 (Div. 1) E. The Child and Binary Tree (R3100)

形式的冪級数の練習! 問題へのリンク 問題概要 各 に対して、次の問に答えよ。 二分木 (完全二分木でなくてもよいし、頂点数も未定) であって、 各頂点の重みが のいずれか 各頂点の重みの総和が であるようなものの個数を 998244353 で割ったあまりを求め…

AOJ 2958 Tree (HUPC 2019 day2-G)

二乗の木 DP を応用したもの。このセットの運営チームだった。 問題へのリンク editorial 北大アーカイブ 問題概要 頂点からなる木が与えられる。 この木の 個の空でない部分グラフの組であって、各部分グラフがいずれも連結で、どの二つの相異なる部分グラ…

Codeforces Grakn Forces 2020 G. Clusterization Counting (R2700)

めちゃ好きだけど、実装重い 問題へのリンク 問題概要 頂点の重み付き無向完全グラフが与えられる。各 に対して、 頂点集合を 個の互いに disjoint な集合に分割する方法であって どの同族辺 (両端点が同一のグループに属する辺) の重みも、どの異族辺 (両端…

AOJ 3190 Ribbons on A Perfect Binary Tree (AUPC 2020 day3-F)

こういうのは探索順序を適切に定めることがめっちゃ重要! 問題へのリンク 問題概要 高さ の完全二分木と、 長さが 2 のリボンが 本 長さが 4 のリボンが 本 ... 長さが のリボンが 本 が与えられる。各リボンは、完全二分木において「葉」と「葉」を始点と…

AtCoder ABC 138 D - Ki (緑色, 400 点)

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