DP状態:state
AtCoder
JOI
JOIG
JOIG春合宿
JOI難易度8
中堅以上の典型要素を詰め合わせた教育的問題
DP
DP高速化
DP高速化:セグメント木
セグメント木
【問題集】セグメント木の入門
0と1と2の問題
操作
操作:区間
最小回数・最小個数を求める
操作:削除
最小コスト
最適化問題
区間分割の仕方を走査する問題
区間分割型ナップサックDP
DP状態:state
RMQ
セグメント木を用いた DP 高速化！ 問題へのリンク editorials 問題概要 'R' と 'G' と 'B' のみからなる長さ の文字列 が与えられる。以下の操作を繰り返し行うことで、"RGB" を繰り返す文字列となるようにしたい。 (操作) 連続する 個以下の文字を消す 目…
AtCoder
JOI
JOIG
JOI難易度9
DP
BFS
LCS型DP
LCS
DP状態:state
スライドbitDP
DP状態:ビット
文字列
部分列
最小回数・最小個数を求める
制約条件:隣接する要素について
最適化問題
いかにも JOI にありがちな添字の持ち方をする DP！ 問題へのリンク 問題概要 英小文字と英大文字からなる長さ の文字列 と、長さ の文字列 が与えられる。また 0 以上 3 以下の整数 が与えられる。 次の条件を満たす文字列 の長さの最小値を求めよ。 は、英…
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 問題！ 問題へのリンク 問題概要 長さ の数列 がある (負値もありうる)。これらの数列をいくつかの連続する区間に分割する。 区間分割の仕方を最適化したときの、各区間における「最大値と最小値の差」の総和として、考えられる最大値を…
Codeforces
DP
区間分割型ナップサックDP
区間
DP状態:state
負値が本質的に効く問題
絶対値やminを扱う問題
最大値の最大化
最適化テク:「最大値の最大化」に基づく緩和
DP高速化
DP高速化:直前との比較のみでよい
DP状態:長さの総和
数列
二値パラメータ問題
テク:|x|=max(-x,x)
DP状態:ビット
最大スコア
マルチテストケース問題
ナップサックDP
区間分割の仕方を走査する問題
最適化問題
つい最近 CodeQUEEN 決勝 E 問題でも出てきた「最大値の最大化」典型テクニック！！！！ 問題へのリンク 問題概要 長さ の 2 つの数列 と が与えられる。今、互いに disjoint な区間群 をとる ( は自由)。ただし、区間の長さの総和がちょうど となるようにす…
