制約条件:グラフの次数列
Codeforces
グラフ問題
NP困難(特殊構造なので解ける)
クリーク
後退解析
queue
葉から考える
制約条件:グラフの次数列
どちらかの条件を満たすものの構築
Yes/No判定問題
復元
1つ求める
定数倍高速化
部分グラフ列挙問題
見積り大事
O(√N)まで考えれば十分
CodeforcesDIV1-B
CodeforcesR2600
TLE が厳しくて話題になってた 問題へのリンク 問題概要 頂点数 、辺数 の単純無向グラフ [tex G] が与えられる。また、正の整数 が与えられる。 以下のいずれかの条件を満たすものが存在するかどうかを判定し、存在するならばそれを出力せよ。 type 1: の…
AtCoder
AtCoder800点
ARC-F
数え上げ問題
全域木の数え上げ問題
グラフ問題
グラフ・盤面・数列の個数の数え上げ
制約条件:グラフの次数列
多項式・形式的冪級数
形式的冪級数の高等演算
木
二項係数
式変形
橙色diff
全域木を考える
コンテスト本番、こっちをやればよかった...ところで解説が天才すぎる! 問題へのリンク editorial 問題概要 個の部品と、 個の接続用部品とがある。これらを用いてフィギュアを作ろうとしている。 番目の部品には 個の穴がついている。接続用部品は、2 個の…
ARC 106 F に関連して、頂点次数制約のついた全域木の個数を求める問題がまさにあったので、その解説を。 問題へのリンク editorial 問題概要 (New Year Contest 2015 E - ひも) 頂点数が であるような完全グラフの全域木であって、以下の条件を満たすものが…