2020-03-07から1日間の記事一覧
Codeforces
操作
数列
辞書順
ConvexHullTrick
stack
非自明な線形時間
操作を好きな回数だけ行える
操作:区間
操作の流れを単純化する
区間分割型ナップサックDP
入れ子構造
Greedy
操作:上書き
平均値に関する問題
CodeforcesDIV1-C
CodeforcesR2100
操作後の結果の最適化問題
操作をstackを用いて高速化する
Greedy:辞書順最小を求める
これが R2100 って嘘でしょ...R2500 くらいに感じる...こどふぉ民の感覚って... 問題へのリンク 問題概要 長さ の数列 が与えられる。以下の操作を好きな順序で好きな回数だけ行える。その結果として考えられる辞書順最小なものを求めよ。 数列の任意の区間…
Codeforces
DP状態削減テク:全部分集合でなく個数のみ持つ
DP
探索順序を工夫して解く
bitDP
N個からK個を選ぶ設定の問題
ナップサックDP
二項係数
CodeforcesDIV2
CodeforcesR2300
DP状態:ビット
数列
最大スコア
制約条件:disjoint
最適化問題
これは楽しい!!! 順番をうまく決めれば、全部の情報を持たなくても、個数のみの情報に落とせる系。 問題へのリンク 問題概要 要素の数列 と、 の二次元数列 が与えられる。 個の の中から 個を選び、 残りの 個の index の中から 個分、 の行ベクトルを選…
Codeforces
全部混ぜて解く
座標圧縮
二分探索
セグメント木
非自明なモノイド
数列
クエリ処理問題
操作:上書き
期待値
主客転倒
差分更新
データ構造
クエリ:削除
二分探索:lower_bound
CodeforcesDIV2
CodeforcesR2800
実装がエグエグのエグだけど、実はなんと、遅延評価セグ木すら必要なくて、普通のセグ木だけあれば解けてしまう! 問題へのリンク 問題概要 個の整数 に対して定まる量 を次のように定義する: の部分集合を選ぶ 通りの方法から一様ランダムに選んで、さらに…