2020-09-27から1日間の記事一覧
AtCoder
AtCoder600点
ABC-F
ABC-like
FFT
数え上げ問題
DP
DP高速化:FFT
マージテク
二項係数
高速畳み込み計算
集計処理
グルーピングの数え上げ問題
ハフマン符号
priority_queue
データ構造
Greedy
橙色diff
二分木のような計算順序
グルーピング(算数)
分割統治法
高度典型
中堅以上の典型要素を詰め合わせた教育的問題
こういうのは包除原理しかない! 問題へのリンク 問題概要 人の人がいる。 人 の身長は である。以下の条件を満たすように、 組のペアを作る方法は何通りあるか、998,244,353 で割ったあまりを求めよ。 どの人もちょうど一つのペアに含まれる。 どのペアも、…
AtCoder
AtCoder500点
ABC-E
ABC-like
セグメント木
遅延評価
データ構造
数値を表す文字列同士の比較
前処理
級数和を求める
クエリ処理問題
青色diff
操作:区間
操作
クエリ:区間
中堅以上の典型要素を詰め合わせた教育的問題
操作:上書き
遅延評価セグメント木
【問題集】遅延評価セグメント木
【問題集】セグメント木のステップアップ
まさに遅延評価セグメント木の練習問題!!! 問題へのリンク 問題概要 長さ の文字列 S がある。 最初は のすべての文字が 1 である。以下の 回のクエリに答えよ。 各クエリは整数 が与えられる () の 番目から 番目までをすべて に書き換える を数値とみな…
AtCoder
AtCoder400点
ABC-D
ABC-like
DP
DP高速化
in-place DP
DP高速化:セグメント木
数列
転倒数
制約:数値が10^6以下
バケット
部分列
セグメント木
データ構造
水色diff
LIS を求める in-place DP を応用すればできる! でも、400 点問題で「DP 配列をセグ木に乗せて」「in-place に更新することで高速化する」という問題が出るとは思わなかった! in-place DP に馴染みのない方は先にこっちを qiita.com 問題へのリンク 問題概…
AtCoder
AtCoder300点
ABC-like
ABC-C
Union-Find
連結成分
DFS
BFS
グラフ
データ構造
茶色diff
【問題集】グラフの入門
そのまま覚えたい典型問題
Union-Find の練習問題という雰囲気ながら、DFS や BFS でも解ける 問題へのリンク 問題概要 頂点数 、辺数 の単純無向グラフが与えられる。これに最小本数の辺を追加することで全体が連結となるようにしたい。その最小本数を求めよ。 制約 考えたこと 全体…