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