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