NoviSteps4D
Dilworthの定理
DAGの最小パス被覆
双対性
最大安定集合・最小点被覆・最小辺被覆
最大安定集合問題
推移性に着目する
二部グラフ
二部マッチング
マッチング
フロー
【問題集】フローのチャレンジ
【問題集】フローのステップアップ
NoviSteps4D
AtCoder
AtCoder625点
橙色diff
ABC-G
文字列
文字列検索問題
SuffixArray
N個の文字列の問題
連続部分列を扱う問題
最大スコア
最適化問題
テク:グラフの問題として考える
Dilworth の定理から、DAG の最小パス被覆!! かつて流行った高度典型。 問題へのリンク 問題概要 個の文字列 が与えられる。各文字列には重み がついている。 これらの文字列から「どの 2 つの文字列も互いに他を部分文字列として含まない」という条件を満…
行列
行列累乗
主客転倒
個別の要素の動きに注目する
順列
期待値
期待値の線形性
操作
操作後の結果を求める問題
操作後の結果の数え上げ
絶対値やminを扱う問題
操作:swap
数え上げ問題
数え上げ問題を期待値に帰着する
操作をちょうどK回行う
係数を考える
累積和
AtCoder
AtCoder700点
ARC-D
橙色diff
NoviSteps4D
行列累乗した。デバッグに手こずった。 問題へのリンク 問題概要 の順列 が与えられる。以下の操作を 回行う。 を選んで と を swap する 操作列は 通り考えられるが、それぞれについての の総和を 998244353 で割った余りを求めよ。 制約 考えたこと の期待…
競プロ典型90問
AtCoder
競プロ典型90問とその類題
競プロ典型90問難易度7
漸化式
DP
行列
行列累乗
ダブリング
整数を「10倍してaを足す」で捉える
DP状態:あまり
sparseな問題
DP高速化:FFT
FFT
DP高速化:きたまさ法・Bostan-Mori法
数え上げ問題
DP高速化:ダブリング
DP状態:どの桁まで見たか(広義の桁DP)
NoviSteps4D
きたまさ法によく似たタイプの DP ダブリング高速化! ただかなり難しい問題だと思うので、004 まで順調に解いていた方が、この問題で挫折しないように注意!!! 無理に解こうとせずに飛ばすのも一案だと思います...... 問題へのリンク editorial 問題概要 …