前提条件 C++14での使用 バグは保証しません(個人的なものなので) 数学 最大公約数・最小公倍数 (gcd, lcd) 約数列挙 (divisor) 逆元 (modinv) 二項係数の剰余 (modcomb) 累乗の剰余 (modpow) 素数判定 (is_prime) 素数テーブル (prime_table) 素因数分解 (p…

目的 木(N頂点N-1辺であり、各頂点に必ずアクセスできるグラフ)の直径を求める。 直径とはグラフの最遠距離である。 関数 build( ): 木の直径を返す。path には直径を構成する辺が格納される。 コード template< typename T = int > struct TreeDiameter : G…

要約 ・コンテスト期間中に問題追加された場合は、contest.acc.jsonを直接編集し、$ acc add --force コマンドを実施する。 背景 E869120氏主催の「競プロ典型90問」を、AtCoderのジャッジを利用して挑戦中。 qiita.com atcoder.jp 普段自分はatcoder-cliとo…

目的 負辺のないグラフで単一始点全点間最短路を求めるアルゴリズム. 各地点でもっとも近い頂点から距離が確定していく. 距離順でソートされたヒープを用いると, 効率よく距離を確定していくことができる. オーダー O(ElogV) 条件 dijkstra(g, s): 重み付き…

説明 グラフを扱う際のテンプレート。 コード template <typename T = int> struct Edge { int from, to; T cost; int idx; Edge() = default; Edge(int from, int to, T cost = 1, int idx = -1) : from(from), to(to), cost(cost), idx(idx) {} operator int() const { retur</typename>…

目的 二次元格子状領域において、幅優先探索を行う。 また、要素xと要素yそれぞれが属するグループを併合することが可能。 オーダー O(HW) 条件 grid_bfs(s, start, wall):= グリッド s 上にある文字 start からすべてのマスへの最短距離を求める。wall には…

目的 アルファベットを一文字ずつ順に出力する。 コード 小文字 for (int i = 0; i <= ('z' - 'a'); i++) { char tmp=(char)('a' + i); } 大文字 for (int i = 0; i <= ('Z' - 'A'); i++) { char tmp=(char)('A' + i); } コードテスト #include <bits/stdc++.h> using names</bits/stdc++.h>…

目的 要素xと要素yが同じグループに属するかどうかを判定するためのデータ構造。 また、要素xと要素yそれぞれが属するグループを併合することが可能。 関数 root(x)：xの根を返す。 unite(x,y)：xとyを併合する。 same(x,y)：xとyが同じ木に属するならtrue,…

目的 stringの文字列を大文字または小文字に揃える。 コード string s; transform(s.begin(), s.end(), s.begin(), ::toupper);//大文字に変換 transform(s.begin(), s.end(), s.begin(), ::tolower);//小文字に変換 コードテスト #include <bits/stdc++.h> using namespace</bits/stdc++.h>…

目的 環境変えても貼り付けるだけにしたい コード #include <bits/stdc++.h> using namespace std; typedef long long int ll; typedef pair<ll, ll> p_ll; typedef vector<pair<ll, ll>> vec_p; //vector<pair<ll, ll>> pairs(n) ,pairs.at(i) = make_pair(i*i, i) #define ture ture #define flase false #de</pair<ll,></pair<ll,></ll,></bits/stdc++.h>…

目的 mod m の世界において、aに対する逆元a-1を計算する。 これを利用することで、剰余同士の割り算が可能になる。 制約 aとmは互いに素である。 オーダー コード //拡張ユークリッド互除法 long long int ext_gcd(long long int a, long long int b, long …

目的 1～Nまでの素数を判定し、vector型に収納する。 素数であれば1を、合成数であれば0を返す。 オーダー O(N log logN) コード vector<bool> prime_table(int n) { vector<bool> prime(n + 1, true); if (n >= 0) prime[0] = false; if (n >= 1) prime[1] = false; for</bool></bool>…

目的 約数をvectorに保存する。 制約 コード vector<long long> divisor(long long n) { vector<long long> ret; for (long long i = 1; i * i <= n; i++) { if (n % i == 0) { ret.push_back(i); if (i * i != n) ret.push_back(n / i); } } sort(begin(ret), end(ret)); return (</long></long>…

目的 素数であればtrue、そうでなればfalseを返す。 オーダー O(√N) コード bool is_prime(long long x) { for(long long i = 2; i * i <= x; i++) { if(x % i == 0) return false; } return true; } 出典 ei1333.github.io

目的 累乗を素数で割った際の剰余を求める。 コード long long modpow(long long a, long long n, long long mod) { long long res = 1; while (n > 0) { if (n & 1) res = res * a % mod; a = a * a % mod; n >>= 1; } return res; } コードテスト #include <iostream></iostream>…

目的 素因数分解をする。 オーダー O(√N) コード vector<pair<long long, long long>> prime_factorize(long long N) { vector<pair<long long, long long>> res; for (long long a = 2; a * a <= N; ++a) { if (N % a != 0) continue; long long ex = 0; // 指数 // 割れる限り割り続ける while (N % a == 0) { ++e</pair<long></pair<long>…

目次 nCk n～107程度 nCk n固定,k～105程度 nCk n～106程度 ACL使用ver 1. nCk n～107程度 目的 二項係数nCkを素数pで割った際の剰余nCk mod pを求める。 制約 p：素数 1≦k≦n≦107 n

目的 最大公約数と最小公倍数を求める。 コード long long int gcd(long long int a, long long int b) { return b ? gcd(b, a % b) : a; } //AとBの最大公約数(A>0, B>0) long long int lcm(long long int a, long long int b){ return a / gcd(a, b) * b; …