Posts

文字列のリスト $(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$ の倍数．...

小さい整数のベクトルの実装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 (有限集合の部分集合) 多重集合のハッシュ (例題 )

自分用の 行列ライブラリ のメモです． 依存関係 AO.cc (Algebra Operations) に依存する … と思う (最近チェックしていない．ひょっとしたら違うかも) 型 要素の型を T として，Matrix<T> が，行列の型になる． 以下，要素の型を T とし，MyMat = Matrix<T> と定義されているものとする． mat は MyMat 型とする． 使用法 using MyMat = Matrix<ll>; MyMat mat1(n, m); REP(i, 0, n) REP(j, 0, m) cin >> mat1.rs(i, j); MyMat cvec1(n, 1); REP(i, 0, n) cin >> cvec1.rs(i, 0); auto cvec2 = mat1 * cvec1; REP(i, 0, n) cout << cvec2.at(i, 0) << " "; cout << endl; 行列を作る m 行 n 列の零行列 MyMat mat(m, n); 各要素を指定したものにする． MyMat mat(m, n); REP(i, 0, m) REP(j, 0, n) mat....

ポインタベースの Trie ライブラリ． ソース ポイント ポインタと new で実装．Trie という構造体がノードを表す． 実装上のノードは増やす一方で，削除はしない． 「そのノードに要素があるか」と「そのノード以下の部分木に存在する要素の数」は，自動で取れる． ノードに存在する要素数は 0/1．マルチセットではない． その他の操作をしたければ，自分で定義する．(user というフィールドが Trie 構造体にある) 使用法 auto root = new Trie<26, 'a'>(); auto p1 = root->insert("abcde"); // 挿入．必要なノードを作ると同時に，「要素」としても登録． auto p2 = root->search("abc"); // 要素ではないので p2 == nullptr auto p3 = root->search("abcde"); // 要素なので，p3 == p1 auto p4 = root->get_node("abc"); // 要素かどうかに関係なくノードを取る // ノードがないときには nullptr が返るが，この場合 "abcde" ノードがあるので "abc" ノードもある assert(p3->reside); // p3が表す文字列は要素である． assert(not p4->reside); // p4が表す文字列は要素でない． root->insert("abab"); assert(root->size_st == 2) // 部分木に存在する要素の数．マルチセットでないことに注意 p3->erase(); // 要素としての削除．葉であってもノードは削除しない． assert(not p3->reside); assert(p4->size_st == 1); // p1 から root まで辿るループ for (auto p = p1; p; p = p->parent) { /* p に対する処理を書く */ } // 文字列 s の全prefixを処理するループ for (auto [p, i] = make_pair(root, 0); true; p = p->get_child_val(s[i++], true)) { /* 長さ i の prefix に対する処理を書く */ if (i == ssize(s)) break; } // 文字列 s のprefixのうち，要素になっているものを処理するループ for (auto [p, i] = make_pair(root, 0); p; p = p->get_child_val(s[i++])) { if (p->reside) { /* 長さ i の prefix に対する処理を書く */ } if (i == ssize(s)) break; } インタフェース テンプレートパラメタ template < int bt_size, // 文字種 char from, // 最初の文字 typename User = monostate, // ユーザデータの型 typename S = string, // 管理するデータの型．string とか vector<char> とか bool compact = 2 < bt_size, // 省メモリ型 bool has_offset = true // オフセットの管理方法 > struct Trie { bt_size … 文字種．小文字の文字列なら 26, 01列なら 2 など． from … 最初の文字．小文字なら 'a', 01文字列なら '0'，整数の01列なら 0 など． User … ユーザデータの型．引数無しで構築できなければならない．省略値は monostate で，これは，何も要素を持たない構造体． S … この trie で管理するデータの型．たいてい string だろうけれど，vector<int> とかでも可．ただし，値は from から from + bt_size までで，char の範囲に入っていること． compact … たとえば全ノードに長さ26のベクトルを持たせるというのはちょっと無駄なので，ここを true にすると，もう少し領域を節約する．ただし，少しは遅くなる (そんなには遅くないと思う)．false にすると，固定長 array になる． has_offset … ノードに，何文字目であるかを持たせるかどうか．これはノードごと 4 バイトしか違わないので，いつでも true でも良かったか…....

概要 Stern Brocot Tree を扱うライブラリを書いた． Stern Brocot Tree 連分数 $$ a_0 + \cfrac{1}{a_1 + \cfrac{1}{\ddots a_{n - 1} + \cfrac{1}{a_n}}} $$ を，$[a_0, a_1, \dots, a_n]$ と書く．各 $a_i$ は，非負整数． $x + 1 = x + \cfrac{1}{1}$ だから，$[a_0, a_1, \dots, a_n]$ と $[a_0, a_1, \dots, a_n - 1, 1]$ は同じ数を表す． これを除くと表現は一意になる．そこで，$[a_0, a_1, \dots, a_n]$ の表現では，$a_n \neq 1$ と約束する． 例外として，$1$ は，$[1]$ で表現する． 連分数 $\alpha = [a_0, a_1, \dots, a_n]$ に対して， $u(\alpha) = [a_0, a_1, \dots, a_n + 1]$ と， $v(\alpha) = [a_0, a_1, \dots, a_n - 1, 2]$ を考える．これは，連分数最後のパートが...

概要 問題へのリンク 公式解説 は，ちゃんと読んでいない． ユーザ解説 で紹介されている解法を読んだ． 次の2つのクエリを処理するものを，Range Parallel Unionfind (仮称) というらしい merge(a, b, l) : $i \in [0, l)$ について，頂点 $a + i$ と 頂点 $b + i$ の間に辺を結ぶ． leader(a) : 頂点 $a$ を含む連結成分の代表元を返す． この問題は，次のように解ける． $2N$ 頂点のグラフを考える． 気持ちは，前半が $S$ で，後半が $S$ を逆順にしたもの 各 $i$ に対して，回文になるために必要なところ (前半と後半を使う) を線で結ぶ． これは，上の Range Parallel Unionfind の merge(a, b, l) でできる． 頂点 $i$ と $2*N - 1 - i$ を線で結ぶ．これは普通の Unionfind を使う． 回文の一つ外側の文字どうしが同じ連結成分に入っていたら不可能． そうでなければ，辞書順最小のものを求めるために，貪欲に各連結成分の値を決めていく． ということで，Range Parallel Unionfind なるものができれば良い．2つ紹介されている．...

Wavelet 行列ライブラリを書いた． 使用法 vector<ll> vec{...}; WaveletMatrix wm(vec, -1); cout << wm.kth_rank(10, 20) << endl; コンストラクタ WaveletMatrix wm(vec, amax); vec … データを格納したベクトルなど．すべて非負整数であることが必要． amax … 「データがこの値を超えない」という値．-1 を与えると，ライブラリの方で最大値を取ってくれる データメンバ wm.N … データの個数 他にもあるが，使わないと思う． データ値の取得 wm.access(i); i 番目の値を取得する．vec[i] と同じになるはずなので，あまり使いではない． 出現回数 wm.rank(t, r); 区間 [0, r) に t が現れる回数を返す． t は非負整数であればよい． r は，wm.N 以下でなければならない． k番目 wm.kth_smallest(k, l, r); wm.kth_largest(k, l, r); 区間 [l, r) で，k 番目に小さい / 大きい 値を返す． k は 0-indexed. たとえば最小値は kth_smallest(0, l, r)....

set, multiset, priority_queue などの比較関数の指定方法

この組合せで適切かどうか分からないが，こう作った． ライブラリソース 解ける問題 Bellman-Ford アルゴリズム 重み付き有向グラフで，特定の点からすべての点への距離 (パスの重みの和の最小値) を求める． 重みは負でも良い．負閉路があると距離が定義できない ($-\infty$ になる) が，このアルゴリズムはその検出ができる． 計算量は，頂点数 $N$，辺数 $M$ として，$O(NM)$． 牛ゲー 次の制約問題を解く． 変数 $x_i$ ($i = 1, \ldots, n$) に関し，次の制約の下で，$x_n - x_1$ の最大値 (または最小値) を求めよ． $x_{A_j} - x_{B_j} \leq C_j$ $\quad(j = 1, \ldots, m)$ $C_j$ は負でも良い．移項すれば良いので，$x_{A_j} - x_{B_j} \geq C_j$ という制約でも良い． この問題で，求める最大値は，「重み $C_j$ の有向辺 $(B_j, A_j)$ を持つグラフで，$1$ から $N$ への距離」になる (参考リンク )． 次が対応する． 制約を満たせないことと，グラフが負閉路を持つこと いくらでも大きな値を取れることと，グラフで$1$から$N$に到達できないこと 最小値バージョンは，同じ制約の下で $x_1 - x_n$ の最大値を求めて符号を反転すれば良い． 注意: このライブラリでは，Bellman-Ford を用いるので，変数の数$N$，制約の数$M$に対して， $\Omega(NM)$ 時間かかる．制約によっては，(適当な変換をして) ダイクストラなどの 速いアルゴリズムを使う必要があるかもしれない．...

問題概要 問題へのリンク 整数 $N$，$M$ と列$L$，$R$，$S$ が与えられる． $M$個の制約 $$\sum\{ A_j \mid j = L_i, \dots, R_i \} = S_i$$ を満たす長さ $N$ の正の整数の列 $A$ が存在するかどうか判定し， 存在する場合には $A$ の総和の最小値を求めよ． 制約 $1 \leq N, M \leq 4000$，$1 \leq S_i \leq 10^9$ 解 公式解説 略解．click to open 牛ゲー．累積和 $B_i := \sum\{A_j \mid 0 \leq j < i\}$ に関して，次を解けば良い． 次の条件の下で，$B_{N + 1} - B_{1}$ を最小化する $B_{i + 1} - B_i \geq 1$ $B_{R_{i} + 1} - B_{L_i} \geq S_i$ $B_{R_{i} + 1} - B_{L_i} \leq S_i$

問題概要 問題へのリンク 整数 $n$, $m$, $k$ と，長さ $k + 1$ の整数の組の列 $((x_1, y_1), (x_2, y_2), \dots, (x_{k + 1}, y_{k + 1}))$ が $(x_i, y_i)$ は，サイズ $n\times m$ のグリッドのセルの座標であり，重複は無い． $(x_i, y_i)$ と $(x_{i + 1}, y_{i + 1})$ の間に1つずつセルを挿入して， 縦横につながった単純パスを作る方法の数 (作れなければ $0$) を mod $10^9 + 7$ で求めよ． 制約 $1 \leq n, m \leq 1000$， $nm \geq 3$，$1 \leq k \leq \lfloor (nm - 1) / 2 \rfloor$ 解 tutorialへのリンク 略解．click to open $P_i = (x_i, y_i)$ と書く．$\{|x_i - x_{i + 1}|, |y_i - y_{i + 1}|\}$ は， (1) $\{0, 2\}$ であるか，(2) $\{1, 1\}$ であるか，でなければならない． 間に入れる点は，(1) では1つに決まる．(2) では，2つの点のうちのどちらか．...