制約条件:距離K以下の2頂点
AOJ
JAG
グラフ問題
三角不等式
グラフの考えるべき辺数を減らす
Union-Find
解に確実に含まれる要素を列挙する
DAG
DP
最長路問題
制約条件:距離K以下の2頂点
AOJ-ICPC500点
JAG夏合宿
AOJ-ICPC
個人的要復習
素直に考えるとグラフの辺数が のオーダーになってしまうので、いかに削減するかを考える問題だった 問題へのリンク editorials 問題概要 頂点数 、辺数 の単純無向グラフが与えられる。各頂点 には値 が振られている。今、各頂点にスコア を割り振りたい。…
AOJ
HUPC
フロー
マッチング
NP困難(特殊構造なので解ける)
二部グラフ
グラフ問題
前処理
最短路問題
前処理:Floyd-Warshall法
Floyd-Warshall法
最大安定集合・最小点被覆・最小辺被覆
制約条件:距離K以下の2頂点
アルファベットは 26 文字!26 は偶数! 問題へのリンク 問題概要 (意訳) 頂点数 、辺数 の無向単純グラフ が与えられる。各頂点 には、1 文字の英小文字 が振られている。ここで正の整数 が与えられ、改めて次のように定義されるグラフ を考える の頂点集合…
AtCoder
AtCoder500点
ABC-E
二項係数
数え上げ問題
木
グラフ問題
木DP
各地点について自由度を掛け算していく数え上げ
木上で配っていくDP
水色diff
制約条件:距離K以下の2頂点
木の走査って 根の方から情報を配っていく 子ノードたちの情報を引っ張ってくる (いわゆる木 DP) という二つの方向性があって、状況に応じてうまいこと使い分けるとよいイメージがある。 問題へのリンク 問題概要 頂点の木があたえられる。木の各頂点を 色に…
順位表メタ読みスキルも大事かもしれない。「たくさん通しているのだから、きっと単純な方法があるに違いない」という感じの 問題へのリンク 問題概要 頂点の連結な無向グラフのうち、その間の最短経路長が 2 となっているような二頂点の組がちょうど 組であ…