極大なものを考える
AtCoder
AtCoder700点
ARC-E
赤色diff
極大なものを考える
LIS
グラフ・盤面・数列の個数の数え上げ
期待値
in-place DP
DP高速化
DP
区間DP
番兵法
順列
探索順序を工夫して解く
BIT
DP高速化:セグメント木
データ構造
セグメント木
回数の期待値
入れ子構造
変なところでハマらないようにしたい... 問題へのリンク 問題概要 の順列 が与えられる。いま、これらの順列の各要素に印をつけていくことを考える。ただし、「印のついた要素が左から順に単調増加となるように並んでいる」という条件を常に満たす必要がある…
AOJ
JAG
DP
探索順序を工夫して解く
ナップサックDP
DEGwerさんの数え上げテクニック集の例題
数え上げ問題
極大なものを考える
条件の言い換え
部分和
ある量を固定して考える
累積和
左右両端からの結果を前処理
AOJ-ICPC500点
JAG夏合宿
AOJ-ICPC
これ面白い!! 問題へのリンク editorials 問題概要 個の正の整数 と、正の整数 が与えられる。 個の整数の中からいくつか選ぶ方法のうち、以下の条件を満たすものの個数を 1000000007 で割ったあまりを求めよ。 選んだ数の総和は 以下である 選んだ数の総…
AtCoder
AtCoder600点
ABC-D
左右両端からの結果を前処理
累積和
各kに対して
N個のものうち1個を変更・削除したものを解く
戻すDP
DP
前処理
条件の言い換え
二分探索
bitベクター高速化
単調性に着目する
数列
ナップサックDP
部分和
極大なものを考える
黄色diff
ARC-D
めっちゃいろんな解法がある! 各 i に対して i 番目を抜いた部分の解を求める系 左右から累積和 戻す DP 単調性を見抜いて二分探索 問題へのリンク 問題概要 個の整数 がある。これらの整数の部分集合のうち、数の総和が 以上になるものをよい集合と呼びま…