2023-09-04から1日間の記事一覧
AtCoder
有志コン
そのまま覚えたいシンプル設定の中堅以上の典型問題
最大値の最大化
最適化テク:「最大値の最大化」に基づく緩和
DP
ナップサックDP
DP状態:on/off
DP状態:state
DP高速化:直前との比較のみでよい
区間分割型ナップサックDP
DP高速化
f(i,j)をiとjとに分離する
数列
Monge性
DP高速化:Monge性の活用(LARSCH)
最適化テク:緩和しても良い
最大スコア
区間分割の仕方を走査する問題
区間
操作をstackを用いて高速化する
DP高速化:stackの活用
stack
最適化問題
これは学びの深い DP 問題！ 問題へのリンク 問題概要 長さ の数列 がある (負値もありうる)。これらの数列をいくつかの連続する区間に分割する。 区間分割の仕方を最適化したときの、各区間における「最大値と最小値の差」の総和として、考えられる最大値を…
AtCoder
AtCoder600点
ABC-G
黄色diff
期待値
期待値の線形性
テク:総和がNになる整数組の種類数はO(√N)
二項係数
多項式・FPS(形式的冪級数)
多項式:PolynomialTalyorShift
色に関する問題
各kに対して
N個からK個を選ぶ設定の問題
種類数
有理数mod998244353
最初 DP で迷走して、期待値の線形性を使って まで来れた。でも、Polynomial Taylor Shift なる解法もあるらしい！ 問題へのリンク 問題概要 個のキャンディがあって、各キャンディの色は正の整数 で表されている。 各 に対して、 個のキャンディから 個のキ…
