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