Posts

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. 典型的な使用法 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....

自分用の 二分探索ライブラリ のメモです． 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) は呼ばれない．...

拡張ユークリッドアルゴリズムのメモ (といっても，Wikipedia を参照するだけ) 参照先 Wikipediaの記事 ポイント 与えられた $a$, $b$ に対して，$g := \text{gcd}(a, b)$ と $sa + tb = g$ となる $s$，$t$ を求める． $a$, $b$ は正，負，0 いずれも可． ただし，$\text{gcd}(a, 0) = \text{gcd}(0, a) = a$ $|s| \leq \max(|a|, |b|)$，$|t| \leq \max(|a|, |b|)$ が成り立つ． $|a|$ や $|b|$ が 64 ビットで表せていれば，このアルゴリズムで得られる $|a|$，$|b|$ もそうなる． ($|sa|$ や $|tb|$ ははみ出すかもしれない) アルゴリズム概要 1 * a + 0 * b = a と，0 * a + 1 * b = b から始める． $s_i a + t_i b = z_i$ と $s_{i + 1} a + t_{i + 1} b = z_{i + 1}$ まで得られたとする． 右辺の割算 $z_i = p z_{i + 1} + q$ をする． ($i$ の式) $ - p \times (i + 1$ の式) を作って， $(s_i - p \, s_{i + 1}) a + (t_i - p \, t_{i + 1}) b = q$ を得る． 右辺が $g := \text{gcd}(a, b)$ になるまで繰り返す． なお，もう一回まわすと $s_{k + 1} a + t_{k + 1} b = 0$ になり，$|s_{k + 1}| = |a|/g$，$|t_{k + 1}| = |b|/g$ が成り立つ． コード util....

全方位木ライブラリ使用法のメモ

前提 自然数 $N$ に対して，$\bar{N} := \{0, 1, \dots, N - 1\}$ とする． $x \leq y$ なる $(x, y) \in \bar{N} \times \bar{N}$ に対する 述語 $P(x, y)$ が，次を満たすとする． $P(x, y)$ かつ $x \leq x’$，$y’ \leq y$ ならば，$P(x’, y’)$ このとき，やはり $(x, y)$ に対して定まる値 $F(x, y)$ について， $\bigoplus \{ F(x, y) \mid P(x, y) \}$ を求めるのが問題． $\oplus$ は，和や最小値や最大値など． ここで，$P(x, y)$ は，$P(x - 1, y)$ や $P(x, y - 1)$ などから，少ない手間で求められるものとする． 考え方 1つの while ループで書く． $P(x, y)$ が成り立ったら，次は $P(x, y + 1)$ を調べる． 成り立たなかったら，次は $P(x + 1, y + 1)$ を調べる． $P(x, y)$ が成り立ったら， $F(x, y) \oplus F(x + 1, y) \oplus \dots \oplus F(y, y)$ を答えに加える． 擬似コード ll i = 0, j = 0; // (i, j) を調べる． ll ans = oplus の単位元; ll a = 初期値, b = 初期値; // F(i, j) や P(i, j) を計算するのに必要な値を用意しておく． // ここでは a, b とする．この位置で用意するのは，(0, 0) 用． while (true) { // 一つのループ if (i > j) { // 例外的処理 // P(i, i) が成り立たないことがある場合，このアルゴリズムは，i > j となる組に来る． // この場合は，単に j を増やす． j++; }else if (calc_P(a, b)) { // P(i, j) が成り立ったら v = calc_val(a, b); // F(i, j) oplus F(i + 1, j) oplus ....

オフライン動的連結ライブラリです

Undo付きUnionFindライブラリです．

ローリングハッシュライブラリの使い方についての自分用のメモです

自作セグメント木ライブラリ の使い方についての自分用のメモです． 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.query(il, ir); $il$ 以上 $ir$ 未満の値に add を適用した結果を返す．...

他サイトへのリンクを並べる Prüfer sequence プリューファー列 (ラベル付き木の列挙に使う) の紹介． ケイリーの公式 ($n$頂点のラベル付き木の個数は$n^{n-2}$) と， ラベル付き木のランダム生成の話が書いてある．

AtCoderでは C++ で boost が使えるので，多倍長計算をすることができます． ヘッダ部分 先頭付近に次のように書いておきます．(競技プログラミングなので，これで良いことにしてください．) #include <boost/multiprecision/cpp_int.hpp> // 整数を使う時 #include <boost/multiprecision/cpp_bin_float.hpp> // 浮動小数点数を使う時 using namespace boost::multiprecision; 整数 多倍長整数として，cpp_int というものが用意されています．普段 int とか long long と書くところを，cpp_int にすればOKです．コンストラクタには文字列も使えます． 例 「AtCoder Regular Contest 057-C 2乗根 」を解いてみたコードです． template<typename T> T power(T a, ll b) { T twoPow = a; T rv = 1; while (b > 0) { if (b & 1LL) rv *= twoPow; twoPow *= twoPow; b >>= 1; } return rv; } cpp_int solve() { string s; cin >> s; cpp_int lo(s); // 読み込んだ文字列をcpp_intに変換 cpp_int lo2 = lo * lo; cpp_int hi2 = (lo + 1) * (lo + 1); cpp_int th = power(cpp_int(100), s....

無向グラフの二重連結に関して，辺二重連結，橋，点二重連結，関節点，block-cut tree などに関するまとめです

ABC306G Return to 1 の解法です

nまでの約数の個数の表と，求めるためのコード