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 へのイタレータ．...

デバッグに失敗した，ないし，長時間かかった間違いの記録 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. できること 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....

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

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

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

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

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

問題へのリンク 状況 コンテスト中解けず．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. 整数版 以下では，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) は呼ばれない．...