Senの競技プログラミング備忘録

こけた問題を自分用の解説で載せる。けんちょんさんのブログを目指したい。質的にも量的にも。こけた問題だけに限定するけど

Codeforces Round #595 (Div. 3) - F. Maximum Weight Subset

codeforces.com 概要 サイズNの木が与えられて、それぞれの頂点には重みがweight[i]だけ設定されている。 あなたは、この中から次の条件を満たすように、好きなだけ頂点を選べる。選んだ頂点たちの重みの総和の最大値を求めよ。 選んだ頂点たちはお互い距離…

Codeforces Round #629 (Div. 3) - E. Tree Queries

codeforces.com 概要 サイズNの木が与えられる。根を頂点1とする。 次のようなM個のqueryに答えよ。 k個の頂点を与える。頂点1からある頂点vへ行くパスからの距離が、k個の頂点すべてに対して、1以下となるvが存在するのならばYES、ないのならNOと答えよ。 …

ABC160 - F - Distributing Integers

atcoder.jp 概要 サイズNの木が与えられる。頂点に1~Nの番号が振られている。k=[1, N]として次の条件下で問題を解け。 頂点kに最初に赤色を塗る。次に塗ることができるのは、すでに塗った頂点に隣接する頂点、というルールのもとで色を塗るとき、何通りの塗…

Codeforces Round #628 (Div. 2) - C. Ehab and Path-etic MEXs

codeforces.com 概要 サイズNの木が与えられる。そのN-1本の辺に、それぞれ1つずつ、0~N-2の数字を重複なく割り当てていく。 頂点uと頂点vの間を通る単一のパス(木なので必ず存在する)上の辺に含まれる数の集合をSとする。Sに含まれない、最小の非負整数をME…

AGC017 - D - Game on Tree

atcoder.jp 概要 サイズNの木が与えられ、頂点には1~Nまでの番号が振られてる。AliceとBobはAliceからゲームを始め、自分の手番が終わったら、相手に交代する。自分の手番では、次の操作を行う。 木の辺を1本取り除く。これによって、木は2つの部分木に分…

ABC149 - F - Surrounded Nodes

atcoder.jp 概要 サイズNの木が与えられる。それぞれの頂点を1/2の確率で白、1/2の確率で黒と塗る。 黒で塗られた頂点をすべて含む最小部分木を考える。その最小部分木のサイズの期待値を求めよ。制約: 1