Posts

std::map に「挿入か更新をする」ときの idiom をすぐに忘れてしまうのでメモしておく． std::map<S, T> mp; と宣言されているとする． 1. 無条件で，s の値を t にする 通常は次で良い: mp[s] = t; もともと s が有ったか無かったのかも知りたい場合や，s へのイタレータも欲しい場合には，次のようにする: auto [it, b] = mp.insert_or_assign(s, t); b には，挿入が行われたかどうかが設定されるので，b が false なら，もともとキー s が存在していたことがわかる．it は s へのイタレータ． 2. キー s が無ければ，値を t にする． 次のように書くと，s の探索が2回走ってしまう． if (mp.find(s) == mp.end()) mp[s] = t; 次のようにすれば 1回ですむ． mp.emplace(s, t); もともと s が有ったか無かったのかも知りたい場合や，s へのイタレータも欲しい場合には，次のようにする: auto [it, b] = mp.emplace(s, t); b には，挿入が行われたかどうかが設定されるので，b が false なら，もともとキー s が存在していたことがわかる．it は s へのイタレータ．...

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

デバッグに失敗した，ないし，長時間かかった間違いの記録 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 あさかつ...

階段関数を表現するライブラリ intervalSet の説明です．

ダブリングを行うライブラリを書きました．ソースはこちら ． できること その1 $f : [0, N) \to [0, N)$ が与えられた時， $r \in [0, R]$ と $i \in [0, N)$ に対して $f^{r}(i)$ を 計算する． 典型的には: $N$ は $10^5$ くらい，$R$ は $10^{18}$ くらい，または $N$ も $R$ も $10^5$ くらいだが，何回も (たとえば $10^5$回くらい) 計算する その2 上の $f$ の他に，モノイド $(M, \oplus)$ と $m: [0, N) \to M$ が与えられて， $r, i$ に対して $\bigoplus_{k = 0}^{r - 1} m(f^{k}(i))$ を計算する． 使用法 その1 DoublingFRel オブジェクト d を作る． 上記 $R$，$N$，$f$ を doubling_from_func に与える． ll R = 100000, N = 100000; auto f = [&](ll i) -> ll { return (i * i) % N; }; auto d = doubling_from_func(R, N, f); 関数 $f$ の代わりにベクトルなどのコンテナを与えたいときには，doubling_from_container を用いる． ll R = 100000, N = 100000; vector<ll> vec(N); REP(i, 0, N) vec[i] = ....

復元方法も含めた最長増加部分列に関するまとめ

集合のハッシュに関する記事です

平方分割ライブラリを書きました

木DP と マージテクを使って解くときのコードスニペット

$$ \binom{n}{r} = \binom{n - 1}{r - 1} + \binom{n - 1}{r} $$ 言わずもがな．パスカルの三角形 $$ \binom{n}{r} = \frac{n}{r} \binom{n - 1}{r - 1} $$ 定理から明らか． $$ \sum_{i = r}^{n} \binom{i}{r} = \binom{n + 1}{r + 1} $$ Hockey-stick identity. 次のように1を繰り返し適用． $\binom{n + 1}{r + 1} = \binom{n}{r} + \binom{n}{r + 1} = \binom{n}{r} + \binom{n - 1}{r} + \binom{n - 1}{r + 1} = \binom{n}{r} + \binom{n - 1}{r} + \binom{n - 2}{r} + \binom{n - 2}{r + 1} = \dots$...

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

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

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....