Posts

他サイトへのリンクを並べる 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までの約数の個数の表と，求めるためのコード

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

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

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

経緯 よく考えればもちろん作れるのだけれど，すぐ間違うのでメモをしておきます． 公式 $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 ライブラリで素数以外の法に関してできること

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

ダブリングを行うライブラリを書きました．自分用のメモです． できること その1 $f : [0, N) \to [0, N)$ が与えられた時， $f^{r}(i)$ を，$r \in [0, R]$ と $i \in [0, N)$ に対して計算する． 典型的には: $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} m(f^{k}(i))$ を計算する． 使用例 その1 ll R = 100000, N = 100000; auto f = [&](ll i) -> ll { return i * i % N; }; DoublingFRel d(R, N, f); ll r = 12345, i = 54321; cout << d....

二項係数に関する公式です．

setw(int n) 桁数を n にする setfill(char c) 余った場所を c で埋める． oct 8進にする hex 16進にする dec 10進にする fixed 固定小数点表示にする scientific 浮動小数点表示にする

インタラクティブな問題がたまに出題される． 特別扱いする必要があるか，ということだが， 何も考えずに書いてしまうとデバッグが難しい，ということがあるので， やはり形式を整えておきたい感じである． 先日の Codeforces R.812 (Div 2) Tournament Countdown で，TLE というめにあった． virtual base class を持つオブジェクトのメソッド呼び出しがあったりしたのが 良くなかったのではないかと思う． ということで，軽く実行できるようにしたい． ポイントとしては，ask() 関数と answer() 関数を用意する． これらで，問と答の入出力部分をラップする． 実装するときには，ask_i() と answer_i() という名前で書く． 通常はこちらを ask(), answer() として使い， 自動テストのと期には ask_judge(), answer_judge() に切り替える． 典型的な実装はこんな感じ．二分探索数当てゲームを想定． bool judge = false; ll ask(ll x) { return judge ? ask_judge(x) : ask_i(x); } ll answer(ll x) { if (judge) answer_judge(x); else answer_i(x); } ll ask_i(ll x) { cout << "? " << x << endl; string s; cin >> s; if (s == "SMALL") return -1; else if (s == "LARGE") return 1; else if (s == "EQUAL") return 0; else assert(0); } void answer_i(ll x) { cout << "!...