2020-10-03から1日間の記事一覧
AOJ
HUPC
DP
木
木DP
二乗の木DP
グルーピングの数え上げ問題
数え上げ問題
ナップサックDP
木DPのノード更新にDP
グラフ
グルーピング(算数)
【問題集】木DPのステップアップ
中堅以上の典型要素を詰め合わせた教育的問題
そのまま覚えたいシンプル設定の中堅以上の典型問題
二乗の木 DP を応用したもの。このセットの運営チームだった。 問題へのリンク editorial 北大アーカイブ 問題概要 頂点からなる木が与えられる。 この木の 個の空でない部分グラフの組であって、各部分グラフがいずれも連結で、どの二つの相異なる部分グラ…
Codeforces
Kruskal法
最小全域木
必要条件を列挙したら十分条件になる
条件の言い換え
グラフ
密グラフ
木
グラフの辺数を削減する
二乗の木DP
木DP
木DPのノード更新にDP
DP高速化:FFT
FFT
Union-Find
最適化テク:最適解の形を考える
各kに対して
数え上げ問題
グルーピング(算数)
グルーピングの数え上げ問題
探索順序を工夫して解く
DP
Union-Findのマージ過程を表す木を考える
最適化テク:解を変形していく(最適性を失わずに)
全域木を考える
CodeforcesOthers
CodeforcesR2700
個人的要復習
Union-Find上のDP
思わず解きたくなる興味深い良問
【問題集】木DPのステップアップ
グラフの辺数削減テク:スーパー頂点を用いてsparseに
めちゃ好きだけど、実装重い 問題へのリンク 問題概要 頂点の重み付き無向完全グラフが与えられる。各 に対して、 頂点集合を 個の互いに disjoint な集合に分割する方法であって どの同族辺 (両端点が同一のグループに属する辺) の重みも、どの異族辺 (両端…
Codeforces
分割統治法
2^K
構築
入力が定数個
数列
操作
操作:上書き
数学的帰納法に基づく考察
再帰的構造に着目する
漸化式
見積り大事
過半数に関する考察
CodeforcesOthers
CodeforcesR2300
ならば になるネタ、結構見る! 問題へのリンク 問題概要 数列 があって、初期状態では となっている。ここで 2 つの正の整数の組 に対して正の整数 を返す関数 を考える。 次の条件を満たす操作列を構築せよ。1 つの操作は整数 で与えられ、 , をともに で…