d_tutuz https://blog.hatena.ne.jp/d_tutuz/ 数学/競プロメモ https://tutuz.hateblo.jp/ グラフ 構築 問題 長さ n の文字列 s が与えられる。以下の条件を満たす n 頂点の木を構築することができるかどうか。 頂点 s_i の文字が 1 であれば、木から辺を 1 つ取り除いて、長さ i の連結成分を作ることができる 頂点 s_i の文字が 0 であれば、木から辺を 1 つ取り除いて、長さ i の連結成分を作ることができない ※ i は 1-indexed 考え方 まず、木を構築するための必要条件を整理する。以下の条件を満たす場合は目的の木を構築することはできない。 が (サイズ の木は作ることはできない) が ( 本切ることで必ずサイズ の木は作るカットが存在する) (あるカットでサイズ の… 190 <iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2Ftutuz.hateblo.jp%2Fentry%2F2018%2F09%2F30%2F085446" title="ARC103-E:Tr/ee(700) - 数学/競プロメモ" class="embed-card embed-blogcard" scrolling="no" frameborder="0" style="display: block; width: 100%; height: 190px; max-width: 500px; margin: 10px 0px;"></iframe> https://cdn-ak.f.st-hatena.com/images/fotolife/d/d_tutuz/20180930/20180930085454.png Hatena Blog https://hatena.blog 2018-09-30 08:54:46 rich https://tutuz.hateblo.jp/entry/2018/09/30/085446 1.0 100%