2021-08-12から1日間の記事一覧
AOJ
JAG
JAG春冬コン
グラフ
指数探索系問題
グラフの頂点集合の部分集合を走査する
確率
bitDP
O(3^N)
連続量問題
グラフのconnectivity
思わず解きたくなる興味深い良問
浮動小数点型を扱う問題
ABC 213 G の類題に挙がっていたのでやってみた！ 問題へのリンク 問題概要 頂点数 、辺数 の単純無向グラフが与えられます。また 以上 以下の整数 が与えられます。 グラフの各辺は % の確率でそれぞれ独立に消失します。グラフ全体が連結である確率を求め…
AtCoder
AtCoder600点
ABC-G
橙色diff
部分グラフ列挙問題
数え上げ問題
グラフ
指数探索系問題
bitDP
高速ゼータ変換
グラフのconnectivity
グラフ・盤面・数列の個数の数え上げ
一般化した問題を解く
包除原理
除原理
グラフの頂点集合の部分集合を走査する
各kに対して
場合分け
SubsetConvolution
高速畳み込み計算
O(3^N)
補集合を考える
個人的要復習
面白かった！！ より一般化した問題 (グラフの頂点集合の任意の部分集合に対して、それらを連結にする辺の選び方の数え上げ) を考えた方が考えやすいね。 問題へのリンク 問題概要 頂点数 、辺数 の単純無向グラフ が与えられます。 の辺集合の部分集合 ( 通…
AtCoder
AtCoder500点
ABC-F
黄色diff
LCP
SuffixArray
文字列
prefixとsuffix
条件の言い換え
解空間:O(N^2)通りの選択肢
stack
入れ子構造
非自明な線形時間
priority_queue
ランレングス圧縮
ならし計算量解析
区間
各kに対して
前処理
左右からそれぞれ走査する
差分更新
変数変換して扱いやすい同型な問題を見出す
総和を求める
操作をstackを用いて高速化する
これを機会に SA-IS を整備した！ 今回の記事はあくまで自分が読んでわかる以上を目指さない備忘録として。 問題へのリンク 問題概要 2 つの文字列 に対して「先頭何文字が一致しているか」を と表すことにします。 長さ の文字列 が与えられます。 の 文字…
