DP状態:最後の場所
AtCoder
AGC-C
AtCoder1100点
橙色diff
DP
DP状態:最後の場所
DP高速化:セグメント木上のin-placeDP
in-place DP
DP高速化:しゃくとり法
しゃくとり法
DP高速化:累積和
遅延評価セグメント木
NoviSteps3D
2017 年の AGC の問題。現代なら ABC F で出そうだ。 問題へのリンク 問題概要 相異なる 個の整数 を 2 つのグループ X, Y に分けたい。 グループ X では、どの 2 個の要素も差が 以下 グループ Y では、どの 2 個の要素も差が 以下 となるようにする分け方…
Codeforces
数え上げ問題
区間
DP
累積和
DP高速化:累積和
DP高速化
座標圧縮
二項係数
区間分割型シーケンシャルDP
確率
重複組合せ
包除原理
包除原理:DP
数列
グラフ・盤面・数列の個数の数え上げ
各区間から1点ずつとってくる問題
座標圧縮したグリッド上のDP
EducationalCodeforces
CodeforcesR2600
制約条件:xi<=ai
個人的要復習
そのまま覚えたいシンプル設定の中堅以上の典型問題
DP状態:最後の場所
座標圧縮をがんばる 問題へのリンク 問題概要 個の区間 が与えられる。それぞれの区間から一様ランダムに整数を選んでいく。 これが広義単調減少となる確率を求め、それを 998244353 で割ったあまりの形式で求めよ。 制約 考えたこと 区間の幅は大きいが、 …
