DP高速化:FFT
Codeforces
Kruskal法
最小全域木
必要条件を列挙したら十分条件になる
条件の言い換え
グラフ問題
密グラフ
木
グラフの考えるべき辺数を減らす
二乗の木DP
木DP
木DPのノード更新にDP
DP高速化:FFT
FFT
Union-Find
最適解の形を考える
最適性条件を考察する
各kに対して
NTT
数え上げ問題
グルーピング
グルーピングの数え上げ
探索順序を工夫して解く
DP
Union-Findのマージ過程を表す木を考える
めちゃ好きだけど、実装重い 問題へのリンク 問題概要 頂点の重み付き無向完全グラフが与えられる。各 に対して、 頂点集合を 個の互いに disjoint な集合に分割する方法であって どの同族辺 (両端点が同一のグループに属する辺) の重みも、どの異族辺 (両端…
AtCoder
AtCoder600点
ABC-F
ABC-like
NTT
数え上げ問題
DP
DP高速化:FFT
マージテク
二項係数
高速畳み込み計算
集計処理
グルーピング
グルーピングの数え上げ
マッチング
マッチングの数え上げ問題
ハフマン符号
priority_queue
データ構造
Greedy
こういうのは包除原理しかない！ 問題へのリンク 問題概要 人の人がいる。 人 の身長は である。以下の条件を満たすように、 組のペアを作る方法は何通りあるか、998,244,353 で割ったあまりを求めよ。 どの人もちょうど一つのペアに含まれる。 どのペアも、…
AOJ
HUPC
FFT
期待値
期待値の線型性
確率
部分和
DP
DP高速化:FFT
各要素ごとに独立
マージテク
ナップサックDP
NTT
前処理
累積和
制約:数値が10^5以下
一直線上のN点の問題
Greedy
priority_queue
データ構造
ハフマン符号
確かに、えでゅふぉのラス問にありそう！ 問題へのリンク 問題概要 人の選手が距離 のレースを走る。 人目はデフォルトでは距離 1 走るのに 秒かかる。 スタートから距離が のところにアイテムがある。各アイテムは各選手に対して独立に、確率 で減速 (距離 …
NTT と聞いて 問題へのリンク 問題概要 偶数 が与えられる。 十進法表記で () しか登場しない 桁の整数のうち、 前半 桁の各位の和 後半 桁の各位の和 が等しいものが何通りあるか、998244353 で割ったあまりで答えよ。leading zero は OK。 制約 考えたこと…
