部分グラフ列挙問題
AtCoder
AtCoder600点
ABC-G
橙色diff
部分グラフ列挙問題
数え上げ問題
グラフ問題
指数探索系問題
bitDP
高速ゼータ変換
グラフのconnectivity
グラフ・盤面・数列の個数の数え上げ
一般化した問題を解く
包除原理
除原理
グラフの頂点集合の部分集合を走査する
各kに対して
場合分け
SubsetConvolution
高速畳み込み計算
累積和
O(3^N)
補集合を考える
面白かった!! より一般化した問題 (グラフの頂点集合の任意の部分集合に対して、それらを連結にする辺の選び方の数え上げ) を考えた方が考えやすいね。 問題へのリンク 問題概要 頂点数 、辺数 の単純無向グラフ が与えられます。 の辺集合の部分集合 ( 通…
Codeforces
グラフ問題
NP困難(特殊構造なので解ける)
クリーク
後退解析
queue
葉から考える
制約条件:グラフの次数列
どちらかの条件を満たすものの構築
Yes/No判定問題
復元
1つ求める
定数倍高速化
部分グラフ列挙問題
見積り大事
O(√N)まで考えれば十分
CodeforcesDIV1-B
CodeforcesR2600
TLE が厳しくて話題になってた 問題へのリンク 問題概要 頂点数 、辺数 の単純無向グラフ [tex G] が与えられる。また、正の整数 が与えられる。 以下のいずれかの条件を満たすものが存在するかどうかを判定し、存在するならばそれを出力せよ。 type 1: の…
AtCoder
AtCoder1000点
DP
グラフ問題
個数のみわかれば遷移が作れるDP
強連結成分分解
ナップサックDP
数え上げ問題
操作列を数え上げる問題
条件の言い換え
DEGwerさんの数え上げテクニック集の例題
部分グラフ列挙問題
橙色diff
AGC-like
面白かった!!!DEGwer さんの pdf より。 問題へのリンク 問題概要 頂点のグラフが与えられる。初期状態では 1 本も辺が張られていない。 このグラフに、頂点 1 を始点とする長さ のウォークをとり、ウォークに沿って有向辺を張っていく。有向辺の張られた…
AOJ
HUPC
数え上げ問題
入力が定数個
対称性
二項係数
重複組合せ
グラフ問題
サイクル
縦に見るものを横に見る
各要素ごとに独立
ある量を固定して考える
数珠
NP困難(特殊構造なので解ける)
部分グラフ列挙問題
「総和=K」を扱う
ゴリ (prd さん) と一緒に出て楽しかったコンテスト。 そして「グラフのサイクル・パスの列挙」に関する問題は北大セットの定番というイメージになってきた。 問題へのリンク 問題概要 下図のような 角錐が与えられる (底面が 角形で "頂点" の頂点番号を 0 …