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