CodeforcesR2800
Codeforces
DP
二次元グリッド
DP高速化
Monge性
制約条件:総和=K
単調性に着目する
数列
高速畳み込み計算
最適化テク：変形しても悪化しない
戻すDP
分割統治法
N個のものうち1個を変更・削除したものを解く
シーケンシャルDP
部分和
CodeforcesDIV1-D
CodeforcesR2800
から落とせる気がまったくしなかった... 問題へのリンク 問題概要 個の広義単調増加数列 が与えられる。 それぞれの数列から、先頭から 個ずつとってきた値の総和の最大値を求めよ。ただし でなければならないものとする。 制約 考えたこと 個数に関する con…
Codeforces
全部混ぜて解く
座標圧縮
二分探索
セグメント木
非自明なモノイド
数列
クエリ処理問題
操作:上書き
期待値
主客転倒・寄与分解
データ構造テク：差分更新
データ構造
操作:削除
二分探索:lower_bound
CodeforcesDIV2
CodeforcesR2800
実装がエグエグのエグだけど、実はなんと、遅延評価セグ木すら必要なくて、普通のセグ木だけあれば解けてしまう！ 問題へのリンク 問題概要 個の整数 に対して定まる量 を次のように定義する: の部分集合を選ぶ 通りの方法から一様ランダムに選んで、さらに…
Codeforces
最大公約数
ある値を固定して考える
解空間:O(N^2)通りの選択肢
数列
数学(整数問題)
互いに素
バケット
調和級数
包除原理
約数系包除
Greedy
枝刈り
stack
データ構造
エラトステネスの篩
メビウス関数
ならし計算量解析
約数
データ構造テク：前処理
制約:数値が10^6以下
最大公約数の値を固定して考える
個人的要復習
高速メビウス変換
CodeforcesDIV2
CodeforcesR2800
思わず解きたくなる興味深い良問
高度典型
操作をstackを用いて高速化する
勉強になった...けど、これ知らずにできるもんなの！？ 問題へのリンク あと、LCM の最小値バージョンもある！ drken1215.hatenablog.com 問題概要 個の正の整数 が与えられる。これらから 2 個選んで LCM をとってできる 個の整数の最大値を求めよ。 制約 …
Codeforces
期待値
競技数学色強め
連続量問題
期待値の線形性
順列の数え上げ
DP
箱根駅伝DP
区間
被覆する方法の数え上げ
二項係数
数え上げ問題
被覆
図形的量の期待値
CodeforcesDIV2
CodeforcesR2800
こういうのに慣れて行きたい。 問題へのリンク 問題概要 長さ の線分上に、ランダムな区間を 個とったときの、区間が 本以上重なっている部分の長さの期待値を求めよ (998244353 で割った余りの形式で)。 なお、区間のランダムな選び方とは、線分から 2 点ず…
