Posts

ダブリングを行うライブラリを書きました．ソースはこちら ． 1. できること 1.1 基本用法 $f : [0, N) \to [0, N)$ が与えられた時， $r \in [0, R]$ と $i \in [0, N)$ に対して $f^{r}(i)$ を 計算する． 1.2 追加用法 上の $f$ とともに，モノイド $(M, \oplus)$ と $m: [0, N) \to M$ も与えられて， $r, i$ に対して $\bigoplus_{k = 0}^{r - 1} m(f^{k}(i))$ も計算する． 典型例: $i \mapsto f(i)$ を1回実行するごとに $m(i)$ だけのコストがかかるとき， $f^r(i)$ の実行に要するコストを求める． $[0..N-1]$ が円環状に並んでいる．$f^r(i)$ の実行で何周するか求める． この場合には，$m(i) := \textrm{ if } r(i) < i \textrm{ then } 1 \textrm{ else } 0$ とすればよい． tree の先祖-子孫パス上の辺の重みの最大値を求める 1....

何のページになるか良く分からないが，希望としては，包除原理を使う問題を集めたい? $x \in \mathbb{N}$ に対して $\bar{x} := \{0, 1, \ldots, x-1\}$ と書く． 定理の言明 $U$ は集合とする．各 $i = 0, \ldots, n-1$ に対して $A_i \subseteq U$ が定められている時， $$ \biggl|\bigcup_{i \in \overline{n}} A_i\biggr| = \sum \left\{ (-1)^{|X| + 1} \biggl|\bigcap_{i \in X} A_i\biggr| \;\middle|\; X \in \mathcal{P}(\bar{n}) \setminus \{ \emptyset \} \right\} $$ 証明は，このブログの中だと ここ にある． 使う問題 ABC456-G Count Holidays 問題へのリンク 次の部分問題を包除原理で解いている: 正整数 $n$ と $k$ が与えられる． 集合 $\bar{n}$ の部分集合 $X$ について，$p(X)$ を，$X$ に含まれる区間の長さの最大値とする． つまり，$i, i + 1, \dots, i + j - 1$ がすべて $X$ の要素になるような $i$ が存在するような $j$ の最大値である． $p(X) \leq k$ であるような $X \subseteq \bar{n}$ の個数を，mod 998244353 で求めよ． 時間計算量 $O(n/k)$．ただし，必要な階乗などは前計算してあって $O(1)$ で得られるとする．...

AtCoder Regular Contest 212 - ARC212 C - ABS Ball の解法です． shobonvip さんによるユーザ解説 そのままみたいなものですが， 式の導出のところを多めに書きました． 問題概要 $N$ 個の区別できない白いボールと，$M$ 個の区別できる箱がある． 「各ボールを赤・青どちらかの色に塗っていずれかの箱に入れる」方法それぞれに対して， $i$ 番目の箱に入った赤，青のボールの数を $a_i$, $b_i$ として $\prod_{1 \leq i \leq M} | a_i - b_i |$ を計算した場合の総和を mod 998244353 で求めよ． 制約: $1 \leq N \leq 10^7$， $1 \leq M \leq 10^7$ 問題へのリンク 解 $a + b = n$ である非負整数 $(a, b)$ についての $|b - a|$ の和を $c_n$ と書くことにすると， 冪級数 $f = \sum_n c_n x^n$ を使って，求める答が $[x^N] f^M$ と表せることに注意する．...

デバッグに失敗した，ないし，長時間かかった間違いの記録 ABC212E Safety Journey 問題へのリンク 2023/07/05 あさかつ 無向グラフが，完全グラフからM本の辺を除いたものとして与えられている． 除く辺は $(u, v)$ の形で与えられている． dp[i][j] = (i 回の繰返し後，頂点 j に到達できる方法の数) という DP で， 全体から 除いた辺の分を引く． $(u, v)$ と $(v, u)$ の両方を引かなければならないところ， $(u, v)$ しか引かなかった． ABC279F BOX 2023/07/05 あさかつ タイプミス 正: if (rx == -1 and ry == -1) { 誤: if (rx == -1 and ry == 1) { ARC164B 2023/07/09 コンテスト 誤読． 正: 木の好きな頂点を選んで出発できる 誤: 木の根から出発する ABC222E Red and Blue Tree 2023/08/02 あさかつ...

順列組合せ・重複ありなし ライブラリに関するメモです．

いろいろな数のだいたいの大きさ，その他

桁DPのコーディングに関する記事です．N 以下の整数で，ある条件を満たすものを数えます．opt さんの記事をもとにしています．

競技プログラミング用に，map と unordered_map がどの程度のサイズまで使えるかを測定した．

文字列のリスト $(s_i \mid i < N)$ をソートする場合の時間計算量についての雑多なまとめ． $S := \sum_i |s_i|$ とする． 1. 辞書順ソート 2つの文字列 $s$, $t$ の比較は，$O(\min(|s|, |t|))$ でできると仮定する． もちろん，全体の計算量が $O(SN \log N)$ であるとはいえる． 1.1 一般 一般のソートアルゴリズムについては，それ以上のことはあまり言えないらしい． 1.2 マージソート 1.2.1 計算量 マージソートならば，計算量は $O(S \log N)$ になる． 全体で $\log N$ 段のマージを行うわけだが，各段の 長さ $L \to 2L$ のマージを考えると， 毎回1つずつが処理されてマージ済の方に送られるのだが，この処理は， どちらの文字列の長さについてもそれ以下のコストで行えるので，とくに，マージ済の方に送られる文字列の 長さ以下のコストである．したがって，このマージにかかるコストは $2L$ 以下であり，つまり， この段のコストは $S$ 以下である． 1.2.2 実装 もちろんマージソートを書いても良いわけではあるが， ABC354-B の解説「文字列をソートする計算量について」 によると，C++ の std::stable_sort は，マージソートで実装されていることが多いそうである． 2. 連結最小 $\sigma = (s_i \mid i < N)$ を任意の順序で連結したときの (辞書順による) 最小のものを求める，という典型問題がある． 関係する問題には，次がある:...

二項係数に関する公式です．

整数の桁を扱うライブラリです．ソースはこちら ． 使用法 digit_util du; // base == 10 digit_util du1(3); // base == 3 digit_util du2(16); // base == 16 du.pow(3) // 1000 du.pow(18) // 1000000000000000000 du.pow_size() // 19, meaning du.pow(i) is valid for i from 0 to 18 du.width(5678) // 4, meaning 5678 has 4 digits du.width(0) // Error. width(n) is defined only for n > 0. du.nd_min(3) // 100, the least number whose width is 3. su.nd_max(4) // 9999, the maximum number whose width is 4....

概要 方程式 $ax \equiv b \pmod M$ の解は，次のように求められる． $g := (a, M)$ として， $g \mid b$ でないとき: 解無し $g \mid b$ であるとき: $a = a’g$， $b = b’g$， $M = M’g$ として，eGCD で，$a’s + M’t = 1$， $0 \leq s < M’$ となる $s, t$ を求める． $b’s \equiv x_0 \pmod{M’}$，$0 \leq x_0 < M’$ となる $x_0$ をとると， 解は，$x_0, x_0 + M’, x_0 + 2M’, \dots, x_0 + (g-1)M’$ の $g$ 個である． 証明 解があるとすると，$ax = b + kM$ と書けるから，$b = ax - kM$ は，$g$ の倍数．...

Cartesian Tree のライブラリ

小さい整数のベクトルの実装2種: small_vector_u64<bits> … unsigned long long の中にビットを分けて格納 small_vector_string … string の各文字に格納 ベクトル自身を safe_umap (unordered_map.cc) などのキーに使える． 使用法 small_vector_u64<bits> small_vector_u64<4> vec1; // 4ビットずつ使用．長さは 64 / bits (この場合は 64/4 = 16) に固定 // 初期値は全要素が0 vec1[0] = 3; vec1[1] = 15; vec1[2] = 20; small_vector_u64<4> vec1{3, 15, 20}; // 上と同じになる． small_vector_u64<4> vec1(vector{3, 15, 20}, 3); // 上と同じになる．第1引数は operator[] を持つこと．第2引数に長さを与える cout << vec1[0] - vec1[2] << endl; cerr << vec1 << endl; // << は定義済 cerr << vec1....

解法に詰まったとき，以下の方法が適用できないか，考えてみる． 二分探索 bit64倍高速化 convolution 半分全列挙 フロー 燃やす埋める 平方分割 CHT trie wavelet 行列 行列累乗 (期待値) = sum_i (i以上になる確率) deque はランダムアクセスが O(1) 区間 [a, b] を2次元平面の点 (a, b) で表現 区間の問題を距離の問題に言い直して Dijkstra (例題 ) 積の和典型 集合のハッシュ． Zobrist Hashing (有限集合の部分集合) 多重集合のハッシュ (例題 )