7K12 blog

猫でも分かるアルゴリズム解説

マクロ一覧

  • ll btest(ll x, ll i): 整数xのi番目ビットが0か1か返す
  • template <class T> void debug(T ... args): デバッグ出力
  • ll divc(ll x, ll y): 除算の天井関数 ceil(x / y)
  • template <ll i, class T> void tsort(T b, T e): tuple(pair) をi番目の要素でソート
#include <bits/stdc++.h>
using namespace std;
//#include <atcoder/all>
//using namespace atcoder;

//#define BOOST
#ifdef BOOST
#include <boost/multiprecision/cpp_int.hpp>
#include <boost/multiprecision/cpp_dec_float.hpp>
#include <boost/integer/extended_euclidean.hpp>
using mpi = boost::multiprecision::cpp_int;
using mpf = boost::multiprecision::cpp_dec_float_100;
#endif

using ll = long long; using ld = long double;
template<class T> using vt = vector<T>; template<class T> using vvt = vector<vector<T>>; using vl = vt<ll>;
using pll = pair<ll, ll>; using plb = pair<ll, bool>; using pcl = pair<char, ll>; using psl = pair<string, ll>;
using vb = vt<bool>; using vc = vt<char>; using vs = vt<string>;
using vpll = vt<pll>; using vpsl = vt<psl>; using vvl = vvt<ll>;
using vvb = vvt<bool>; using vvc = vvt<char>; using vvpll = vvt<pll>;
using dl = deque<ll>; using dc = deque<char>; using dpll = deque<pll>;
using setl = set<ll>; using setc = set<char>; using setpll = set<pll>;
using mapll = map<ll, ll>; using maplb = map<ll, bool>; using mapcl = map<char, ll>; using mapsl = map<string, ll>;
using graph = vvl; using wgraph = vvpll;
#define all(c) (c).begin(),(c).end()                    // begin to end
#define allr(c) (c).rbegin(),(c).rend()                 // rbegin to rend
#define rep(i,b,e) for(ll i=b;i<e;i++)                  // repeat
#define repr(i,b,e) for(ll i=b;e<i;i--)                 // repeat reverse
#define ill(...) ll __VA_ARGS__;in(__VA_ARGS__);        // input long long
#define ild(...) ld __VA_ARGS__;in(__VA_ARGS__);        // input long double
#define ic(...) char __VA_ARGS__;in(__VA_ARGS__);       // input char
#define istr(...) string __VA_ARGS__;in(__VA_ARGS__)    // input string
#define iv(t,name,sz) vt<t>name(sz);in(name)            // input vt<T>
#define ivp(t,name,sz) vt<t>name(sz);inp(name)          // input vt<pair>
#define ivv(t,name,y,x) vvt<t>name(y,vt<t>(x));in(name) // input vvt<pair>
const ll inf = 2000000000000000000;              // infinity
const long long abc_max = 26;                    // alphabet max size
const long long llong_max = 9223372036854775807; // 9 * 10^18
const long double pi = 3.1415926535897932384626; // 3.14 ...
const long double eps = LDBL_EPSILON;            // 2.22e-016
const size_t str_not_find = string::npos;        // string::find()

void in_graph(ll v, ll e, graph& g, ll vfix = 0); // 頂点数v辺数eのグラフ入力
void in_graph(ll v, ll e, wgraph& g, ll vfix = 0); // 頂点数v辺数eのグラフ入力
void in_directed_graph(ll v, ll e, graph& g, ll vfix = 0); // 頂点数v辺数eの有向グラフ入力
void in_directed_graph(ll v, ll e, wgraph& g, ll vfix = 0);  // 頂点数v辺数eの重み付き有向グラフ入力
string stosl(string& s); // 文字列を小文字に変換
string stosu(string& s); // 文字列を大文字に変換
graph to_graph(wgraph& g); // wgraph -> graph
wgraph to_wgraph(graph& g, ll c = 0); // graph -> wgraph
void bit_set(ll& x, ll i, ll b); // 整数xのi番目ビットをbに設定
ll bit_cnt(ll x); // C++20 popcount
ll bit_size(ll x); // 2進数にしたときのサイズを取得
string bit_tostr(ll x); // 整数xをstringに変換
template <class C> ll lcnt(C& c); // c.count()をllで返す
template <class C, class X> ll lcnt(C& c, X x); // c.count(x)をllで返す
ll llog(ll a, ll b, bool u = false); // 底aのlog(b)切り捨て(u = trueならa進数bの桁数と同値)
ll lpow(ll x, ll n); // xのn乗をllで返す
template <class T> ll lsize(T& c); // c.size()をllで返す
template <class T> bool range(ll x, vt<T>& v); // 配列の範囲内チェック
template <class T> bool range(ll y, ll x, vvt<T>& v); // 二次元配列の範囲内チェック
template <class T> bool orange(ll x, vt<T>& v); // 配列の範囲外チェック
template <class T> bool orange(ll y, ll x, vvt<T>& v); // 二次元配列の範囲外チェック
template <class C> void fix_c(C& c, ll fix); // 値の調整
template <class C> void fix_cp(ll fix1, ll fix2, C& c); // 値の調整 (pair)
template <class T> void itr_next(T& itr, ll INF = inf); // イテレータのインクリメント
template <class T> void itr_prev(T& itr, ll INF = -inf); // イテレータのデクリメント
template <class C> auto& rat(C&, ll); // 逆順アクセス
template <class C> auto& rat(C&, ll, ll); // 逆順アクセス
graph reverse_graph(graph& g); // 隣接リストを逆順にする
wgraph reverse_graph(wgraph& g); // 重み付き隣接リストを逆順にする
template <class T1, class ... T2> bool umax(T1& x, T2 ... args); // xを最大値に更新
template <class T1, class ... T2> bool umin(T1& x, T2 ... args); // xを最小値に更新
template <class T> void vvmake(ll ys, ll xs, vvt<T>& vv); // 二次元配列生成
template <class T, class S> void vvfill(T b, T e, S fill); // 二次元配列の初期化

ll btest(ll x, ll i) { return (62 < i) ? 0 : static_cast<ll>(x & (1ll << i)); }
template <class ... T> void debug(T ... args) { for (auto e : { args ... }) cerr << " " << e; cerr << endl; }
ll divc(ll x, ll y) { return x / y + bool(x % y); }
void in(void) {}
template <class H, class ... T> void in(H& head, T& ... tail) { cin >> head; in(tail...); }
template <class T> void in(vt<T>& v) { for (auto& e : v) in(e); }
template <class T> void inp(vt<T>& v) { for (auto& e : v) in(e.first, e.second); }
void in_graph(ll v, ll e, graph& g, ll vfix) { ll a, b; g.resize(v); rep(i, 0, e) cin >> a >> b, a += vfix, b += vfix, g[a].push_back(b), g[b].push_back(a); }
void in_graph(ll v, ll e, wgraph& g, ll vfix) { ll a, b, w; g.resize(v); rep(i, 0, e) cin >> a >> b >> w, a += vfix, b += vfix, g[a].push_back({ b,w }), g[b].push_back({ a,w }); }
void in_directed_graph(ll v, ll e, graph& g, ll vfix) { ll a, b; g.resize(v); rep(i, 0, e) cin >> a >> b, a += vfix, b += vfix, g[a].push_back(b); }
void in_directed_graph(ll v, ll e, wgraph& g, ll vfix) { ll a, b, w; g.resize(v); rep(i, 0, e) cin >> a >> b >> w, a += vfix, b += vfix, g[a].push_back({ b,w }); }
template <class T> void out(T x, ll sp = 0) { cout << fixed << setprecision(sp) << x << endl; }
template <class T> void oendl(T& c) { for (auto& e : c) cout << e << endl; }
template <class T> void ospace(T& c) { ll i = 0; for (auto& e : c) cout << e << ((i++ != lsize(c) - 1) ? " " : ""); cout << endl; }
string stosl(string& s) { string res; for (auto e : s) if ('a' <= e && e <= 'z') res.push_back(tolower(e)); return res; }
string stosu(string& s) { string res; for (auto e : s) if ('a' <= e && e <= 'z') res.push_back(toupper(e)); return res; }
graph to_graph(wgraph& g) { graph res(lsize(g)); for (ll i = 0; i < lsize(g); i++) for (auto& [next, c] : g[i]) res[i].push_back(next); return res; }
wgraph to_wgraph(graph& g, ll c) { wgraph res(lsize(g)); for (ll i = 0; i < lsize(g); i++) for (auto& next : g[i]) res[i].push_back({ next,c }); return res; }
void bit_set(ll& x, ll i, ll b) { (b) ? x |= (1ll << i) : x &= ~(1ll << i); }
ll bit_cnt(ll x) { bitset<64> b(x); return b.count(); }
ll bit_size(ll x) { return llog(2, x, true); }
template <class C> ll lcnt(C& c) { return ll(c.count()); }
template <class C, class X> ll lcnt(C& c, X x) { return ll(count(all(c), x)); }
ll llog(ll a, ll b, bool u) { ll now = 1, res = (u) ? 1 : 0; while (now < b) res++, now *= a; return (now != b) ? res - 1 : res; }
ll lpow(ll x, ll n) { if (x == 2) return (1ll << n); ll z = 1; rep(i, 0, n) z *= x; return z; }
template <class T> ll lsize(T& c) { return ll(c.size()); }
template <class T> bool orange(ll x, vt<T>& v) { return (x < 0 || ll(v.size()) <= x); }
template <class T> bool orange(ll y, ll x, vvt<T>& v) { return (y < 0 || ll(v.size()) <= y || x < 0 || ll(v[y].size()) <= x); }
template <class T> bool range(ll x, vt<T>& v) { return !orange(x, v); }
template <class T> bool range(ll y, ll x, vvt<T>& v) { return !orange(y, x, v); }
template <class C> void fix_c(C& c, ll fix) { for (auto& e : c) e += fix; }
template <class C> void fix_cp(ll fix1, ll fix2, C& c) { for (auto& e : c) { if (fix1 != 0) e.pf += fix1; if (fix2 != 0) e.ps += fix2; } }
template <class T> void itr_next(T& itr, ll INF) { if (*itr != INF) ++itr; }
template <class T> void itr_prev(T& itr, ll INF) { if (*itr != INF) --itr; }
template <class C> auto& rat(C& c, ll i) { return c[lsize(c) - 1 - i]; }
template <class C> auto& rat(C& cc, ll i, ll j) { return cc[lsize(cc) - 1 - i][lsize(cc[lsize(cc) - 1 - i]) - 1 - j]; }
graph reverse_graph(graph& g) { graph res(lsize(g)); rep(i, 0, lsize(g)) for (auto& next : g[i]) res[next].push_back(i); return res; }
wgraph reverse_graph(wgraph& g) { wgraph res(lsize(g)); rep(i, 0, lsize(g)) for (auto& [next, cost] : g[i]) res[next].push_back({ i, cost }); return res; }
template <class T1, class ... T2> bool umax(T1& x, T2 ... args) { if (max({ args ... }) <= x) return false; x = max({ args ... }); return true; }
template <class T1, class ... T2> bool umin(T1& x, T2 ... args) { if (x <= min({ args ... })) return false; x = min({ args ... }); return true; }
template <class T> void vvmake(ll ys, ll xs, vvt<T>& vv) { vv.resize(ys); rep(y, 0, ys) vv[y].resize(xs); }
template <class T, class S> void vvfill(T b, T e, S fill) { for (auto x = b; x != e; x++) std::fill(all((*x)), fill); }
template <ll i, class T> void tsort(T b, T e) { sort(b, e, [&](const auto& l, const auto& r) { return get<i>(l) < get<i>(r); }); }


/**********************************/
/********** BEGIN OF LIB **********/
/**********************************/

namespace LIB {}

/**********************************/
/*********** END OF LIB ***********/
/**********************************/

using namespace LIB;
//using mint = NT_ModINT< 998244353 >;
//using mint = NT_ModINT< 1000000007 >;