DP高速化:しゃくとり法
AtCoder
AGC-C
AtCoder1100点
橙色diff
DP
DP状態:最後の場所
DP高速化:セグメント木上のin-placeDP
in-place DP
DP高速化:しゃくとり法
しゃくとり法
DP高速化:累積和
遅延評価セグメント木
NoviSteps3D
2017 年の AGC の問題。現代なら ABC F で出そうだ。 問題へのリンク 問題概要 相異なる 個の整数 を 2 つのグループ X, Y に分けたい。 グループ X では、どの 2 個の要素も差が 以下 グループ Y では、どの 2 個の要素も差が 以下 となるようにする分け方…
AtCoder
有志コン
DP高速化:セグメント木
セグメント木
しゃくとり法
DP高速化:しゃくとり法
区間
最適化の考察：最適解の形を考える
in-place DP
DP
操作
単純化：操作の流れを単純化して考える
f(i,j)をiとjとに分離する
最適化の考察：変形しても悪化しない
操作:区間
操作:削除
最小コスト
ソートすることが目的の操作の問題
最適化問題
面白かった！セグ木を使ったけど、区間を複数個にする必要がないことから、しゃくとり法で線形でできるね！ 問題へのリンク 問題概要 の順列 が与えられる。以下の操作を繰り返すことで、単調増加となるようにしたい。 区間 の要素をすべて削除する (コスト…
