Posts

ポインタベースの Trie ライブラリ． ソース ポイント ポインタと new で実装．Trie という構造体がノードを表す． 実装上，ノードは増やすだけで，削除はしない． (template parameter で指定する) 3つのモードがある．これらのモードは，メンバ関数 insert / erase / search の振舞に影響する TRIE_SET_SINGLE … set に相当 TRIE_SET_MULTI … multiset に相当 TRIE_SET_NONE … どちらにも該当しない ノードに格納するユーザデータを定義できる (user というフィールドがある) 使用法 using MyTrie = Trie<26, 'a', TRIE_SET_SINGLE>; // 文字種類数，先頭文字，モード MyTrie* root = new MyTrie; // Trie の作成． MyTrie* p1 = root->insert("abcde"); // 挿入．必要なノードを作ると同時に，「要素」としても登録． MyTrie* p2 = root->search("abc"); // 要素ではないので p2 == nullptr MyTrie* p3 = root->search("abcde"); // 要素なので，p3 == p1 MyTrie* p4 = root->get_node("abc"); // 要素かどうかに関係なくノードを取る // ノードがないときには nullptr が返るが，この場合は，p4 == p2 になる． assert(p3->reside == 1); // p3が表す文字列は要素である． assert(p4->reside == 0); // p4が表す文字列は要素でない． root->insert("abab"); root->insert("abab"); // いまは SINGLE なので，何も起こらない assert(root->size_st == 2) // 部分木に存在する要素の数． p3->erase(); // 要素としての削除．葉であってもノードは削除しない． assert(p3->reside == 0); assert(p4->size_st == 1); // 文字列 s の全prefixを処理するループ // 長い方から: for (MyTrie* p = root->get_node(s); p; p = p->parent) // ....

概要 いくつか実装の選択肢があるので迷ってしまうが，次のように決めておくと良いかもしれない． ポインタは常に左から右に動かす．戻らない． 性質が成り立つ境界が2つあるわけだが， どちらの境界でも，静止状態では，ポインタは右側を指すようにする． ポインタが境界の左側を指していたときのなんらかの値が欲しいときには， それをどこかに記録しておく． Rationale 戻すというのは常には可能ではないかもしれないし，戻すとなると右端を減らすという新たな処理が必要． ．決して戻さないと決めておいた方が楽． ポインタを進めてみないと性質が成り立つかどうかわからないということがある． 左側の時の値が欲しい場合は，おそらく，少ない． 注意 つまり，「…がなりたつ最大のr」を求めようとしているときには， 「…が成り立たない最小のr」を求めることになるので，現在の r の値から 1 を引くことになる． 典型実装 $l$ の動く範囲が $[0, N)$ で，$r$ の動く範囲が $[0, N]$ だとする．(こういうことが多いであろう) 「cond() が成り立つ最小のr」 ( cond() がなりたつまで r を増やす ) ll r = 0; for (ll l = 0; l < N; ) { auto cond = [&]() -> bool { /* 条件 */ }; auto incr_r = [&]() -> void { r++; /* そのほか r を増やすときに行うこと */ }; auto incr_l = [&]() -> void { l++; /* そのほか l を増やすときに行うこと */ }; while (r <= N and not cond()) incr_r(); if (r > N) break; do_something(l, r); incr_l(); } 「cond() が成り立つ最大のr」 ( cond() が成り立っている間 r を増やしつづける )...

問題概要 問題へのリンク 種類AのカードがA枚，種類BのカードがB枚ある．一列にランダムに並べる． 正整数 $K$ が与えられる． 左から順にカードを見る． それまでに見た種類Aのカードの枚数を $a$，種類Bのカードの枚数を $b$ とする． $b = a + K$ であれば，スコア $b$ を得て終了する．そうでなければ次のカードに進む． 最後のカードまで見た場合には，スコア $B$ を得て終了する． スコアの期待値を求めよ． 制約 $A \geq 1, B \geq 1$ $1 \leq K \leq A + B \leq 10^7$ 解 次のように言い換えられる: 下図のグリッドで，左下隅から右上隅に (上か右に) 進むパスをランダムに選ぶ． 赤い丸のいずれか最初に到達した点の b 座標をスコアとする． 赤丸 $(a, b)$ に最初に到達するパスを数えられれば良い．$b = a + K$ に乗っている赤丸で考える．(右上隅の赤丸も同様．) $(0, 0)$ から $(a, b)$ へのパスの数から，これらのパスで $(a, b)$ より早く直線を触わるものの数を引けば良いが， これだと考えにくい． $(0, 0)$ から $(a, b)$ へのパスでそれまでに直線を触らないものは，緑の二重丸 $(a, b - 1)$ を通る．したがって， $(0, 0)$ から $(a, b - 1)$ へのパスで，それまでに直線を触らないものを数えても同じ． パスは $\binom{a + b - 1}{a}$ だけあるので，これらのうち，それまでに直線を触ってしまうものを数えて引けば良い．...

Cartesian Tree のライブラリ

ほぼ公式解説のコピーです． 問題概要 問題へのリンク 以下では 0-index とする． 長さ $N$ の整数列 $C$, $G$ で，$0 \leq C_i < N$，$0 \leq G_i < N$ であるものが与えられる． $0, 1, \dots, N - 1$ の順列 $P$ で，すべての $i$ について $C_{P_i} \neq G_i$ となるものの個数を mod 998244353 で求めよ．$1 \leq N \leq 2\times 10^5$． 解 $S_i := \{ P \mid C_{P_i} = G_i \}$ とすれば，求めるものは $\bigcap_{i \in \bar{N}} {S_i}^{\text{C}}$ なので，包除原理により $ \sum \left\{ (-1)^{|X|} \biggl|\bigcap_{i \in X} {S_i} \biggr| \;\middle|\; X \in \mathcal{P}(\bar{n}) \right\} $ を求めれば良い． 包除原理についてはこのblogの記事 参照．...

何のページになるか良く分からないが，希望としては，包除原理を使う問題を集めたい? 記法: $x \in \mathbb{N}$ に対して $\bar{x} := \{0, 1, \ldots, x-1\}$ と書く． 全体集合が文脈から自明なとき，集合 $A$ の補集合を $A^{\text{C}}$ と書く． 集合 $A$ の冪集合を $\mathcal{P}(A)$ と書く． 定理の言明 $U$ を集合とする．各 $i \in \bar{n}$ に対して $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 \{ \varnothing \} \right\} $$ 証明は，このブログの中だと ここ にある． 補集合を考えることによって，次が得られる． 偶奇による符号が反転していることに注意． $X$ が $\varnothing$ である場合も入っていて $\bigcap_{i\in \varnothing} {A_i}^{\text{C}} = U$ であることにも注意．...

自作セグメント木ライブラリ の使い方についての自分用のメモです． 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....

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

自分用の木のライブラリのメモです．ソースはこちら ． 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....

問題概要 問題へのリンク 整数 $N$ と，長さ $N$ の正の整数列 $(A_1, \ldots, A_N)$ が与えられる． $m = 1, 2, \ldots, N$ に対して，次の問題を解け 列 $(A_1, \dots, A_m)$ の空でない部分列のスコアの総和を 998244353 で割ったあまりを求めよ． ただし，列 $(B_1, \ldots, B_k)$ のスコアは，$\displaystyle\sum_{i = 1}^{k-1} \textrm{gcd}(B_i, B_{i + 1})$ である． 制約 $1\leq N \leq 5\times10^{5}$，$1 \leq A_i \leq 10^5$ 解 公式解説へのリンク ユーザ解説 (noshi91) へのリンク すこし考察すると，解を $R_1, \ldots, R_N$ として， $$ R_i = 2R_{i - 1} + \sum_{j = 1}^{i - 1} 2^j \textrm{gcd}(A_i, A_j) $$...

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

ダブリングを行うライブラリを書きました．ソースはこちら ． 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....

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 あさかつ...

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