他サイトへのリンクを並べる 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 ライブラリで素数以外の法に関してできること

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

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

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

燃やす埋める問題についての記事です． 動機 燃やす埋める問題については，一度エントリを書いた のですが，そこにはともかく理解したことを全部書いたので，コンテスト中に参照しても把握するのがたいへん，という状況になってしまっています．そこで，コンテスト中に思い出したい最小限のことだけまとめることにしました． 考え方 問題文中に「$p$ のとき$b$を受け取る」という記載があったら，「先に $b$ を受け取る．$\neg p$ の時 $b$ を支払う」と読み替えて，すべて支払いをすると考える． グラフ全体の source ノードのラベルは True，sink ノードのラベルは False． ノード $p$ からノード $q$ への矢印に，重み $a$ がついているのは，「$p$が成り立つのに$q$が成り立たない場合，コスト $a$ を支払う」と読む． したがって，この図では，以下が表現されている $p_6$ が成り立って，$p_7$ が成り立たなかったら，$a_2$ 支払う． $p_1$ が成り立たなかったら，$a_5$ 支払う． $p_7$ が成り立ったら，$a_3$ 支払う． $p_8$ は成り立つ． $p_9$ は成り立たない． 最小カットが，コスト最小の真偽割当．図の赤線だと，$p_1, \ldots, p_6, p_8$ を真，$p_7, p_9$ を偽にする割当に相当し，この場合のコストは$a_2 + a_6$． 連言や選言のノードは，矢印を出せるか入れられるかが決まっている．下図を参照．不可の理由は，たとえば連言なら，$p$, $q$を真に，$p\land q$ を偽にできてしまうから．(矢印の根本を真にできてしまうと不当な利益がある．矢印の根本を偽にできても嬉しくない) したがって，「$p \land q$ なら，支払を行う」は，表現できない． しかし，$\neg q$ の方を表すノード $r$ を用意すれば， 「$p$ が成り立って $r$ が成り立たなければ，支払を行う」の形で表現できる．

解説ACです