Posts

1000までの素数表 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293, 307, 311, 313, 317, 331, 337, 347, 349, 353, 359, 367, 373, 379, 383, 389, 397, 401, 409, 419, 421, 431, 433, 439, 443, 449, 457, 461, 463, 467, 479, 487, 491, 499, 503, 509, 521, 523, 541, 547, 557, 563, 569, 571, 577, 587, 593, 599, 601, 607, 613, 617, 619, 631, 641, 643, 647, 653, 659, 661, 673, 677, 683, 691, 701, 709, 719, 727, 733, 739, 743, 751, 757, 761, 769, 773, 787, 797, 809, 811, 821, 823, 827, 829, 839, 853, 857, 859, 863, 877, 881, 883, 887, 907, 911, 919, 929, 937, 941, 947, 953, 967, 971, 977, 983, 991, 997, $10^9$ までの素数の分布 $n$ $10^n$ までの素数の数 1 4 2 25 3 168 4 1229 5 9592 6 78498 7 664579 8 5761455 9 50847534

ポテンシャル付きUnionFindです． 使用法 UnionFind uf(N); // 普通のUnionFind (ポテンシャル無し) ld = uf.merge(a, b); // マージ．新しいリーダを返す ld = uf.leader(a); // リーダ ng = uf.num_groups(); // 全体のグループ数 ( == リーダの数) sz = uf.group_size(a); // a が属するグループのサイズ グループの要素のリストを得るためには，前処理として，GroupInfo を作る必要がある． これには，$O(N)$ かかる． auto gi = uf.group_info(); for (int i : gi.group(a)) cout << i << endl; // a が属するグループの要素の列挙 ポテンシャル付きにするためには，テンプレートパラメタで，ポテンシャルの型を渡す． (デフォルトの型は，UFDummyAlg なるものになっている) UnionFind<ll> uf1(N); UnionFind<ftwo> uf2(N); 必要があれば，零元，和，単項マイナスを渡すこともできる: UnionFind<ll> uf3(N, 0LL, plus<ll>(), negate<ll>()); ポテンシャル付きの時には，merge のときの第3引数に，ポテンシャルを渡さなければならない (省略不可) ld = uf....

自分用の 行列ライブラリ のメモです． 依存関係 AO.cc (Algebra Operations) に依存する． 型 要素の型を T として，Matrix<T> が，行列の型になる． (実装上，これは，Mat<AO_def<T>> として定義されているが，使うときは気にしなくて良い) 以下，要素の型を T とし，MyMat = Matrix<T> と定義されているものとする． mat は MyMat 型とする． 構築子 MyMat(int dimI_, int dimJ_) … dimI_ 行 dimJ_ 列 の零行列 MyMat(int dimI_, int dimJ_, T t) … dimI_ 行 dimJ_ 列 の，要素の値がすべて t である行列 MyMat(int dimI_, int dimJ_, const vector<T>& vec) … dimI_ 行，dimJ_ 列で，内部表現が vec である行列． 内部表現は，$a_{00}, a_{01}, \dots, a_{10}, a_{11}, \dots a_{mn}$ の順に並べた1次元 vector....

問題へのリンク 状況 コンテスト中解けず．ACまで結局3時間かかった． 解説を読んで 「辞書順最小の良い整数列」を一度に求めようとしたので話を複雑にしてしまった． 良い整数列を全部求める その中で辞書順最小のものを決める と考えるべきだった． [1] のように問題が与えられた時，[2] のように後ろから最適な場所をマークしていく． [3] の青線が，良い整数列の全部になる．この際，前の段階で「最適」とは言われなかったところも 良い整数列として現れていることに注意． もっとも下にある青線の列が答となる．

ABC346-G Alone の解法です．典型だったのか．知らなかった…. 問題へのリンク ABC346-G Alone 問題概要 $A = (A_1, \dots, A_N)$ が与えられる． $1 \leq L \leq R \leq N$ で，$A_L, A_{L + 1}, \dots, A_R$ の中に1度だけ出現する数がある ような $(L, R)$ の組の数を答えよ． 制約: $N \leq 2\times 10^5$, $1 \leq A_i \leq N$ 前提知識 辺が座標軸と平行な長方形 $N$ 個の頂点の座標が与えられた時， 被覆する図形の面積は，次の方法で $O(N \log N)$ で求められる． 適宜座標圧縮する．頂点のx座標の小さい順にソートして平面走査する．ベクトル $S$ を用意する． 左端頂点 $(x, y_1)$, $(x, y_2)$ が現れたら，$S[y_1], …, S[y_2 - 1]$ に$1$を加える． 右端頂点 $(x, y_3)$, $(x, y_4)$ が現れたら，$S[y_3], …, S[y_4 - 1]$ に$-1$を加える． $S[\min], … S[\max]$ のうち，$0$ であるものの数を $t$ として，$\max - \min + 1 - t$ を答に加える． 愚直だと $\Omega(N^2)$ かかるが，次の lazy segment tree を使うと $O(N \log N)$ になる．...

自分用の木のライブラリのメモです．ソースはこちら ． 1. 典型的な使用法 ll N; cin >> N; Tree tr(N, root); // ノード数 N, 根は root． vector weight(N - 1, 0LL); REP(i, 0, N - 1) { ll a, b, w; cin >> a >> b >> w; a--; b--; // 0-indexed. ll e = tr.add_edge(u, v); weight[e] = w; } auto dfs = [&](auto rF, ll nd) -> void { for (ll cld = tr.children(nd)) { ... } for (auto [cld, e] = tr....

自分用の 二分探索ライブラリ のメモです． 1. 整数版 以下では，INT は，int, long long, unsigned int などを表す． signature template <typename INT> requires integral<INT> INT binsearch(auto check, INT yes, INT no) 引数 check … 判定関数．INT を受け取って bool を返す． yes … 真になる値 no … 偽になる値 制約 check 関数は，以下のいずれかを満たす述語 $P(x)$ を，開区間 (yes, no) において実装したものでなければならない ある $t$ が存在して， $x \leq t$ である $x$ について，$P(x)$ は真． $t < x$ である $x$ について，$P(x)$ は偽． ある $t$ が存在して， $x \leq t$ である $x$ について，$P(x)$ は偽． $t < x$ である $x$ について，$P(x)$ は真． 概念的には，$P(\text{yes})$ は真で，$P(\text{no})$ は偽でなければならない． ただし，実際には，check(yes) や check(no) は呼ばれない．...

拡張ユークリッドアルゴリズムのメモ (といっても，Wikipedia を参照するだけ) 参照先 Wikipediaの記事 ポイント 与えられた $a$, $b$ に対して，$g := \text{gcd}(a, b)$ と $sa + tb = g$ となる $s$，$t$ を求める． $a$, $b$ は正，負，0 いずれも可． ただし，$\text{gcd}(a, 0) = \text{gcd}(0, a) = a$ $|s| \leq \max(|a|, |b|)$，$|t| \leq \max(|a|, |b|)$ が成り立つ． $|a|$ や $|b|$ が 64 ビットで表せていれば，このアルゴリズムで得られる $|a|$，$|b|$ もそうなる． ($|sa|$ や $|tb|$ ははみ出すかもしれない) アルゴリズム概要 1 * a + 0 * b = a と，0 * a + 1 * b = b から始める． $s_i a + t_i b = z_i$ と $s_{i + 1} a + t_{i + 1} b = z_{i + 1}$ まで得られたとする． 右辺の割算 $z_i = p z_{i + 1} + q$ をする． ($i$ の式) $ - p \times (i + 1$ の式) を作って， $(s_i - p \, s_{i + 1}) a + (t_i - p \, t_{i + 1}) b = q$ を得る． 右辺が $g := \text{gcd}(a, b)$ になるまで繰り返す． なお，もう一回まわすと $s_{k + 1} a + t_{k + 1} b = 0$ になり，$|s_{k + 1}| = |a|/g$，$|t_{k + 1}| = |b|/g$ が成り立つ． コード util....

全方位木ライブラリ使用法のメモ

前提 自然数 $N$ に対して，$\bar{N} := \{0, 1, \dots, N - 1\}$ とする． $x \leq y$ なる $(x, y) \in \bar{N} \times \bar{N}$ に対する 述語 $P(x, y)$ が，次を満たすとする． $P(x, y)$ かつ $x \leq x’$，$y’ \leq y$ ならば，$P(x’, y’)$ このとき，やはり $(x, y)$ に対して定まる値 $F(x, y)$ について， $\bigoplus \{ F(x, y) \mid P(x, y) \}$ を求めるのが問題． $\oplus$ は，和や最小値や最大値など． ここで，$P(x, y)$ は，$P(x - 1, y)$ や $P(x, y - 1)$ などから，少ない手間で求められるものとする． 考え方 1つの while ループで書く． $P(x, y)$ が成り立ったら，次は $P(x, y + 1)$ を調べる． 成り立たなかったら，次は $P(x + 1, y + 1)$ を調べる． $P(x, y)$ が成り立ったら， $F(x, y) \oplus F(x + 1, y) \oplus \dots \oplus F(y, y)$ を答えに加える． 擬似コード ll i = 0, j = 0; // (i, j) を調べる． ll ans = oplus の単位元; ll a = 初期値, b = 初期値; // F(i, j) や P(i, j) を計算するのに必要な値を用意しておく． // ここでは a, b とする．この位置で用意するのは，(0, 0) 用． while (true) { // 一つのループ if (i > j) { // 例外的処理 // P(i, i) が成り立たないことがある場合，このアルゴリズムは，i > j となる組に来る． // この場合は，単に j を増やす． j++; }else if (calc_P(a, b)) { // P(i, j) が成り立ったら v = calc_val(a, b); // F(i, j) oplus F(i + 1, j) oplus ....

オフライン動的連結ライブラリです

Undo付きUnionFindライブラリです．

ローリングハッシュライブラリの使い方についての自分用のメモです

自作セグメント木ライブラリ の使い方についての自分用のメモです． AtCoder Library にセグメント木はありますが， それができる前から使っていたものなので… 使用法 値の型を DAT, 更新演算の型を OP とする． 基本のセグメント木 作成 auto st = make_seg_tree(unit_dat, add, init_vec); unit_dat は，加法単位元 add には，加法の演算を行う関数を指定する． 関数ポインタ，クロージャ，関数オブジェクトが使える． init_vec は初期ベクトル 初期ベクトル設定は，分けても良い: auto st = make_seg_tree(unit_dat, add); st.set_data(init_vec); 値の代入 (1点) st.set_single(i, x); # または st.rs(i) = x; $i$ 番目の値として $x$ を設定する． rs は，reference for substitution のつもり． これは，STSubst なるオブジェクトを作成して返す． STSubst オブジェクトには，代入演算子 = が再定義してあって，セグメント木の該当部分を更新するようになっている． 値の取得 (1点) st.at(i); $i$ 番目の値を取得する． 値の取得 (範囲) DAT x = st.query(il, ir); $il$ 以上 $ir$ 未満の値に add を適用した結果を返す．...

他サイトへのリンクを並べる Prüfer sequence プリューファー列 (ラベル付き木の列挙に使う) の紹介． ケイリーの公式 ($n$頂点のラベル付き木の個数は$n^{n-2}$) と， ラベル付き木のランダム生成の話が書いてある．