制約条件:グラフの次数列
AtCoder
AtCoder600点
ARC-D
黄色diff
グラフ問題
木
グラフの考えるべき辺数を減らす
全域木を考える
数え上げ問題
各kに対して
制約条件:グラフの次数列
パリティ
実験
FFT
二分木のような計算順序
priority_queue
連結成分
数学的帰納法
二項係数
サイクル
XOR
Greedy
「選ぶ」と「選ばない」の一対一対応
連結成分ごとに分解して考える
分割統治法
なんとか解けた。若干エスパー気味に解いた。 問題へのリンク 問題概要 頂点数 、辺数 の無向単純グラフが与えられる。 各 に対して、この誘導部分グラフ (頂点集合はそのまま、辺集合は部分集合) であって、次数が奇数の頂点が 個であるようなものの個数を …
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 - ひも) 頂点数が であるような完全グラフの全域木であって、以下の条件を満たすものが…
