2020-09-26から1日間の記事一覧
AtCoder
AtCoder900点
ARC-like
数え上げ問題
期待値
期待値の線形性
順列を題材とした問題
操作
個別の要素の動きに注目する
考察：主客転倒・寄与分解
転倒数
BIT
級数和を求める
データ構造
シャッフル
データ構造テク：差分更新
f(i,j)をiとjとに分離する
橙色diff
操作をちょうどK回行う
操作後の結果を求める問題
有理数mod998244353
コンテスト中に まで導いておきながら、最後詰めきれなかったのは反省。 問題へのリンク 問題概要 の順列 と、2 以上の整数 が与えられる。 に対して順に以下の操作を行う。 をランダムシャッフルする 回の操作後に得られる順列の転倒数の期待値を、mod 9982…
AtCoder
AtCoder800点
ARC-like
数直線上のN点の問題
Greedy
ダブリング
データ構造テク：前処理
累積和テク:左右両端からの累積和や累積結果を前処理
最適化の考察：最適解に必ず含まれる要素を列挙する
考察：必要条件を列挙して十分性を示す
区間
操作:区間
クエリ処理問題
二分探索:lower_bound
最適化の考察：最適解の形を考える
数え上げ問題
操作によって作れるものの集合を考える(判定関数を考える)
N個のものうち1個を変更・削除したものを解く
橙色diff
データ構造テク:「次の要素」へのポインタを求める
累積和テク:累積和や累積結果を前処理しておく
左右からそれぞれ走査する
これは天才！！！ 問題へのリンク 問題概要 一直線上に 個の点が順に並んでいる (座標が )。 個のクエリが与えられる。 各クエリでは区間 () が与えられる 個の点のうち のみを取り出してできる 個の点について以下の問に答えよ 与えられた点集合から、どの …
