Mo’s algorithm のコンテスト用メモです

Educational Codeforces Round 115 F. RBS の解法です． 解説ACです． 問題概要 問題へのリンク 文字 ( と ) のみからなる空でない文字列全体の集合を $S$ とする． $s \in S$ に対し，$s$ の空でない prefix であって， 括弧の対応が取れているものの数を $f(s)$ と書くことにする． 例えば $f(\verb!"()()()))"!) = 3$, $f(\verb!"(()())(("!) = 1$． $S$ の要素が $n$ 個与えられる． これらを並べ替えて連結して得られる文字列 $s$ について，$f(s)$ の 最大値を求めよ． 制約: $ 1 \leq n \leq 20$，与えられる文字列の長さの和は $4\times 10^5$ 以下． 制限時間3秒． 解法 0-index で記述する． $\bar{n} := \{0, \ldots, n-1\}$ とする． $s \in S$ に対し，現れる ( の数から ) の数を引いたものを $g(s)$ と書く． $s \in S$ で，全ての $i < |s|$ に対して $g(s) \geq 0$ であるものの集合を $L$ と書く．$D := S \setminus L$．...

公式解説とは少しだけ異なる解法です

公式解説の行間を埋めました．

高速ゼータ変換について，自分用にまとめた記事です．

AtCoder Regular Contest 137 D - Prefix XORs の解法です． コンテスト中に解いた方法 (実験結果から適当に求める) をベースに， 公式解説を参照して追加しました． リュカの定理の証明もWikipediaを見て書きました． 問題概要 長さ$N$の整数列 $A = (A_1, \ldots, A_N)$ と整数 $M$ が与えられる． 下の操作を$k$回行ったあとの $A_i$ の値を $A(i, k)$ と書くことにする． $k = 1, 2, \ldots, M$ について，$A(N, k)$ を求めよ． 操作: 各$i = 1, 2, \ldots, N$ について， $A_i$ を同時に $A_1 \oplus A_2 \oplus \cdots \oplus A_i$ で置き換える． 制約: $1 \leq N, M \leq 10^6$; $0 \leq A_i < 2^{30}$ 問題へのリンク 解法 実験 $A(i, k)$ は，$A_1, \ldots, A_i$ のいくつかのXORをとったものになる． そこで，$a(i, m, k) \in \{0, 1\}$ をとって， $A(i, k) = \bigoplus_{m=1}^{i} a(i,m,k) A_m$ と書く． 計算してみると分かるとおり，$a(i, m, k)$ は，$i - m$ と $k$ にしか 依存しない．そこで，$b(j, k) := a(j, 0, k)$ と書くことにする． $A(i, k) = \bigoplus_{m=1}^{i} b(i - m, k) A_m = \bigoplus \{ A_{i - j} \mid b(j, k) = 1; j = 0, \ldots, i-1 \}$ だから， 各 $k = 1, 2, \ldots, M$ について，$b(j, k) = 1$ となる $j$ を (高速に) 列挙できれば良い．...

解説ACです．

解説ACです

解説ACです．

最大流と最小カットについてのコンテスト用のまとめです

ABC238G Cubic? の解法です．公式解説と同じです．

素因数分解に要する時間を，事前計算と個別の計算に分けて計測しました

方針にも実装にも時間がかかりました．

パナソニックプログラミングコンテスト2021に参加して，ABCDEF 6完347位でした．A - Water Pressure / B - Election / C - Counting 2 / D - Neighbors / E - Minimal payments / F - Jealous Two

解説ACです．