前提 自然数 $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までの約数の個数の表と，求めるためのコード

ネストしたベクトルは，添字を並べる順序で性能が変わるが，どのように並べれば良いかはよくわからない．

インタラクティブ問題のデバッグ方法

経緯 よく考えればもちろん作れるのだけれど，すぐ間違うのでメモをしておきます． 公式 $d \in \mathbb{Z}$，$t \in \mathbb{R}$ とする． $d \leq t \iff d \leq \lfloor t \rfloor$ $d < t \iff d < \lceil t \rceil$ $t \leq d \iff \lceil t \rceil \leq d$ $t < d \iff \lfloor t \rfloor < d$ 考え方 \begin{eqnarray*} d\leq t &\iff& t \in \{ t \mid d \leq t \} \\ &\iff& t \in \bigcup \{ [e, e+1) \mid e = d, d+1, \ldots \} \\ &\iff& \bigvee \{ t \in [e, e+1) \mid e = d, d+1, \ldots \} \\ &\iff& \bigvee \{ \lfloor t \rfloor = e \mid e = d, d+1, \ldots \} \\ &\iff& d \leq \lfloor t \rfloor \hspace{20em} \end{eqnarray*}...

mod ライブラリで素数以外の法に関してできること

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