座標圧縮したグリッド上のDP
AtCoder
AtCoder600点
ABC-F
ABC-like
積分
橙色diff
テク:K以上からK+1以上を引く
期待値
各区間から1点ずつとってくる問題
区間
連続量問題
座標圧縮
FFT
DP
後ろから解く
差分更新
多項式・FPS(形式的冪級数)
FPS(形式的冪級数)の高等演算
座標圧縮したグリッド上のDP
競技数学色強め
図形的量の期待値
時々やってくる積分ゲー。同時に多項式ゲーでもあった。 問題へのリンク 問題概要 個の区間 が与えられる。これらの区間から一様分布にしたがって点をとってくる (連続値)。 各点の座標の最大値の期待値を をかけた値 (整数値になる) を 1000000007 で割った…
AtCoder
AtCoder700点
座標圧縮
座標圧縮したグリッド上のDP
LIS
全探索
DP
区間分割型ナップサックDP
期待値
数列
グラフ・盤面・数列の個数の数え上げ
各区間から1点ずつとってくる問題
区間
写像12相
ベル数
二項係数
赤色diff
ゲーは確かに面白いかもしれない。 問題へのリンク 問題概要 長さ の整数列 が与えらる。 同じく長さ の整数列 は、 各 について独立に、 を満たす整数の一様分布からランダムに選ばれる。 このとき、 の最長増加部分列の長さの期待値を mod 1000000007 で計…
Codeforces
数え上げ問題
区間
DP
累積和
DP高速化:累積和
DP高速化
座標圧縮
二項係数
区間分割型ナップサックDP
確率
重複組合せ
包除原理
包除原理:DP
数列
グラフ・盤面・数列の個数の数え上げ
各区間から1点ずつとってくる問題
座標圧縮したグリッド上のDP
EducationalCodeforces
CodeforcesR2600
制約条件:xi<=ai
個人的要復習
そのまま覚えたいシンプル設定の中堅以上の典型問題
DP状態:最後の場所
座標圧縮をがんばる 問題へのリンク 問題概要 個の区間 が与えられる。それぞれの区間から一様ランダムに整数を選んでいく。 これが広義単調減少となる確率を求め、それを 998244353 で割ったあまりの形式で求めよ。 制約 考えたこと 区間の幅は大きいが、 …