Posts

問題概要 問題へのリンク 整数 $N$ が与えられる． $1 \leq N \leq 1.2 \times 10^5$ $i = 1, \dots, N$ に対して，整数 $A_i, B_i$ が与えられる．$1 \leq A_i < B_i < 998244353$ $i = 1, \dots, N$ に対して，$A_i, B_i$ のうち一つを独立ランダムに選び，選んだものを昇順に並べるとき， $k = 1, \dots, N$ について，小さい方から $k$ 番目の数の期待値を $\text{mod } 998244353$ で求める． 解 以下，公式解説と2つのユーザ解説の内容をまとめたものを書く． $A_i, B_i$ の全部を小さい順に並べて長さ $2N$ の列 $C_1, \ldots, C_{2N}$ とする． 同じ大きさのものがあっても，適当にタイブレークをする． この $C_j$ が，期待値にどれだけ寄与するか考える． $1/2$ の確率で選ばれない．このときの寄与は $0$． $1/2$ の確率で選ばれる． $j’ = 1, \dots, j - 1$ の中に，$A_i, B_i$ が両方入っている $i$ が $a_j$個， $A_i$ は入っているが $B_i$ は入っていないような $i$ が $b_j$個あったとする． $A_i < B_i$ なので，逆のパターンはない． すると，$C_j$ は，選ばれたものの列で，$a_j + 1$ 番目から $a_j + b_j + 1$ 番目のいずれかになる． $a_j + 1 + t$ 番目になる確率は，($C_j$ 自体が選ばれる確率 $1/2$ も合わせると) $\displaystyle\frac{1}{2^{b_j + 1}}\binom{b_j}{t}$ である． 期待値への寄与は，この確率に $C_j$ をかけたものになる． 多項式で書くと，$k$ 番目の数の期待値への $C_j$ の寄与は， $\displaystyle \frac{1}{2} [x^k] x^{a_j} (\frac{1}{2} (x + 1))^{b_j}$ なので， $\displaystyle \frac{1}{2} [x^k] \sum_{j = 1}^{2N} x^{a_j} (\frac{1}{2} (x + 1))^{b_j}$ を求めれば良い．...

SWAG のライブラリを書きました．ソースはこちら 使用法 auto sw1 = make_swag(plus<ll>(), 0LL); auto sw = make_swag(multiplies<MyMatrix>(), MyMatrix{{1,0},{0,1}}); // operator and its unit element. // operator should be associative. sw.push(obj1); // push obj1 into the queue sw.pop(); // pop the front element T v = sw.get_val(); // calculate the aggregated value e1 `op` e2 `op` ... `op` en // where e1 is the front and en is the back T a = sw.front(); // the front element T b = sw....

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

メモ cmpNaive の judge バージョンを使おうとしているとき，実行前に，din_*.txt でテストをする方法． { cat din_1.txt; ./cans < din_1.txt; } | ./cans naive 複数あるなら: for f in din_*.txt; do echo $f; { cat $f; ./cans < $f; } | ./cans naive ; done

ABC354-G の解答とともに，関連する予備知識 (König の定理, Dilworth の定理) をまとめます

K番目の要素の二分探索による求め方と，ベクトルのt付近の要素

何のページになるか良く分からないが，希望としては，包除原理を使う問題を集めたい? 記法: $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$ であることにも注意．...

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

問題へのリンク 非負整数 $n$ に対して，$\bar{n} = \{0, 1, \dots, n - 1\}$ と書く． 問題の本質部分 正整数 $N$, $M$ と， 各 $i \in \bar{M}$ について，$S_i \subseteq N$ が与えられる． $X \subseteq N$ であって，すべての $i \in \bar{M}$ に対して $X \cap S_i \neq \varnothing$ であるものの数を mod 998244353 で求めよ． 制約 $N \leq 2\times 10^5$，$M \leq 20$， 解法 ほとんど，公式解説 に書いてあることそのままだが， 多少，行間を埋めている． 条件を満たさないものを数えて，$2^N$ から引く．つまり，$i \in \bar{M}$ に対し， $A_i := \{ X \subseteq N \mid X \cap S_i = \varnothing \}$ として， $\text{ans} := |\bigcup_{i \in \bar{M}} A_i|$ を求めることになる．...

ポインタベースの 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) // ....

概要 a <= b なる整数 a, b に関する命題 P(a, b) が単調であるとき，尺取り法を用いることができる．単調な命題は2種類ある． 種類1 (広い方が成り立ちやすい): P(a, b) かつ a’ <= a かつ b <= b’ ならば P(a’, b') 種類2 (狭い方が成り立ちやすい): P(a, b) かつ a <= a’ かつ b’ <= b ならば P(a’, b') 種類1 については「各 a について P(a, b) が成り立つ最小の b を求めたい」， 種類2 については「各 a について P(a, b) が成り立つ最大の b を求めたい」という状況になることが多い． いくつか実装の選択肢があるので迷ってしまうが，次のように決めておくと良いかもしれない． 種類2 についても，￢P を考えることによって，種類1 とみなす． こうすると，P(a, b) が成り立たない最小の b が得られてしまうので，b - 1 が求めるものと考える． a を表す変数は，なるべく for ループで回す．(増分が1にできるとはかぎらないが…....

問題概要 問題へのリンク 種類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-based 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 \subseteq \bar{N} \right\} $ を求めれば良い． 包除原理についてはこのblogの記事 参照．...

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