2020-10-06から1日間の記事一覧
AtCoder
AtCoder600点
ABC-D
累積和テク:左右両端からの累積和や累積結果を前処理
累積和
各kに対して
N個のものうち1個を変更・削除したものを解く
戻すDP
DP
前処理
条件の言い換え
二分探索
bitベクター高速化
単調性に着目する
数列
ナップサックDP
部分和
極大なものを考える
黄色diff
ARC-D
累積和テク:累積和や累積結果を前処理しておく
めっちゃいろんな解法がある! 各 i に対して i 番目を抜いた部分の解を求める系 左右から累積和 戻す DP 単調性を見抜いて二分探索 問題へのリンク 問題概要 個の整数 がある。これらの整数の部分集合のうち、数の総和が 以上になるものをよい集合と呼びま…
AtCoder
AtCoder700点
座標圧縮
座標圧縮したグリッド上のDP
LIS
全探索
DP
区間分割型ナップサックDP
期待値
数列
グラフ・盤面・数列の個数の数え上げ
各区間から1点ずつとってくる問題
区間
写像12相
ベル数
二項係数
赤色diff
ゲーは確かに面白いかもしれない。 問題へのリンク 問題概要 長さ の整数列 が与えらる。 同じく長さ の整数列 は、 各 について独立に、 を満たす整数の一様分布からランダムに選ばれる。 このとき、 の最長増加部分列の長さの期待値を mod 1000000007 で計…