2019-06-21から1日間の記事一覧
AtCoder
AtCoder500点
ABC-E
数え上げ問題
LCS
DP
文字列
数列
ダブルカウントを防ぐ場合分け
累積和
DP高速化
DP高速化:累積和
二次元累積和
青色diff
LCS型DP
共通部分列に関する問題!!!!! 最長共通部分列問題は有名だけど、今回は共通部分列を数え上げる問題。 問題へのリンク 問題概要 2 つの数列 が与えられる。 と の共通部分列が何通りあるかを求めよ。 ただし、 や から抜き取ってできる文字列が同じもの…
二乗の木 DP の例題として、すごくいい感じ!!! 問題へのリンク 問題概要 頂点のツリーが与えられて、各頂点 には 人がいる。いま、人を移動させて、各頂点の人数の最大値と最小値との差が 1 になるようにしたい。 1 人が辺 1 個分を移動するのに必要なコ…
AtCoder
AtCoder900点
ARC-E
二乗の木DP
DP
木
木DP
包除原理
パリティ
包除原理:DP
数え上げ問題
グラフ
グラフ・盤面・数列の個数の数え上げ
木DPのノード更新にDP
ナップサックDP
マッチング
グルーピングの数え上げ問題
前処理
二項係数
赤色diff
【問題集】木DPのチャレンジ
高度典型
すごく典型的な「二乗の木 DP」!!!!! そして包除原理との組み合わせ。 問題へのリンク 問題概要 を偶数とする。 頂点の木が与えられる。 頂点を 組の 2 つペアにする方法のうち、各ペアを結ぶパスをすべて考えたときに全辺が被覆されるようなものの個数…