制約条件:グラフの次数列
次数制約つきのグラフを構築するためには、次数の大きいところから Greedy というよく知られた問題！ 問題へのリンク 問題概要 正の整数からなる長さ の数列 が与えられる。 以下の条件を満たすような、頂点数 のグラフが存在するかどうかを判定せよ。 単純…
プリューファーコードが使える問題！ 今でこそ高度典型となったが、当時は知られていなかった気がする。 問題へのリンク 問題概要 頂点数が であるような完全グラフの全域木であって、以下の条件を満たすものの個数を 1000000007 で割ったあまりを求めよ。 …
DFS などの探索をしても解けるし、単に次数を見るだけでも解ける。 問題へのリンク 問題概要 個の葉をもつスターグラフを、レベル のスターと呼ぶことにする。 高橋君は、はじめ何個かのスターからなるグラフを持っている。これらのスターの頂点数の総和は …
プリューファーコード！ それを知っていれば FPS 解法は自然。 問題へのリンク 問題概要 以上 以下の整数集合の部分集合 {} が与えられる。 頂点に と番号のついた頂点数 の木であって、各頂点の次数が集合 に含まれているようなものの個数を 998244353 で割…
木 DP のいい感じの練習問題だった！ 問題へのリンク 問題概要 頂点数 の重み付き木が与えられる (重みは負のこともある)。 この木の辺の部分集合であって、各頂点 に接続する辺の本数が 本以下であるようなものに対して、辺の重みの総和の最大値を求めよ。 …
なんとか解けた。若干エスパー気味に解いた。 問題へのリンク 問題概要 頂点数 、辺数 の無向単純グラフが与えられる。 各 に対して、この誘導部分グラフ (頂点集合はそのまま、辺集合は部分集合) であって、次数が奇数の頂点が 個であるようなものの個数を …
TLE が厳しくて話題になってた 問題へのリンク 問題概要 頂点数 、辺数 の単純無向グラフ [tex G] が与えられる。また、正の整数 が与えられる。 以下のいずれかの条件を満たすものが存在するかどうかを判定し、存在するならばそれを出力せよ。 type 1： の…
コンテスト本番、こっちをやればよかった...ところで解説が天才すぎる！ 問題へのリンク editorial 問題概要 個の部品と、 個の接続用部品とがある。これらを用いてフィギュアを作ろうとしている。 番目の部品には 個の穴がついている。接続用部品は、2 個の…
ARC 106 F に関連して、頂点次数制約のついた全域木の個数を求める問題がまさにあったので、その解説を。 問題へのリンク editorial 問題概要 (New Year Contest 2015 E - ひも) 頂点数が であるような完全グラフの全域木であって、以下の条件を満たすものが…
ラグランジュ緩和か、、、 しかしこれ、ある特定の 1 頂点について次数が 以下であるような最小全域木を求める問題とみなせるわけだけど、こんなんが解けるのは面白い。 全域最小木スライドにある通り、全頂点について次数が 以下となるような最小全域木を求…
