JOIG春合宿
AtCoder
JOI
JOIG
JOIG春合宿
JOI難易度8
中堅以上の典型要素を詰め合わせた教育的問題
DP
DP高速化
DP高速化:セグメント木
セグメント木
【問題集】セグメント木の入門
0と1と2の問題
操作
操作:区間
最小回数・最小個数を求める
操作:削除
最小コスト
最適化問題
区間分割の仕方を走査する問題
区間分割型ナップサックDP
DP状態:state
RMQ
セグメント木を用いた DP 高速化! 問題へのリンク editorials 問題概要 'R' と 'G' と 'B' のみからなる長さ の文字列 が与えられる。以下の操作を繰り返し行うことで、"RGB" を繰り返す文字列となるようにしたい。 (操作) 連続する 個以下の文字を消す 目…
AtCoder
JOI
JOI難易度8
JOIG
JOIG春合宿
テク:区間をsetで管理する
Greedy
Greedy:交換しても悪化しない
Greedy:今が良いほど未来も良い
区間
区間ソート
N個の区間の問題
disjointな区間の集合を管理する問題
探索順序を工夫して解く
priority_queue
区間スケジューリング
各区間から1点ずつとってくる問題
ならし計算量解析
被覆
最大スコア
最適化テク:解を変形していく(最適性を失わずに)
座標圧縮
最適化問題
JOI ではお馴染みの「 個の区間を扱う問題」。ただし実装がしんどかった。僕は区間を set で管理する方法で実装した。 問題へのリンク editorials 問題概要 制約 考えたこと いかにも貪欲法の香りが漂っている問題ですね。この手の問題では、 個の区間を終端…