祝！テンプレート肥大化!
このブログには僕しか住んでいない気が･･･
にじさんじ箱推しガチ勢ガナリヤです。
今回は、自分の使用しているテンプレートが自分でも管理しきれなくなったため、公開しつつ見直していこうと思います。
この記事の一番下にお借りしたサイトなどを記述させていただきます。
まずは全体のソースコードを貼っていこうと思います。
はえ〜すっごい長い
でも、コンパイルは余裕で通るし、コード読みやすくなるしええやろ！（無謀）
少しずつパーツごとに見ていこうと思います！
include
//include //------------------------------------------ #include <vector> #include <list> #include <map> #include <climits> #include <set> #include <deque> #include <stack> #include <bitset> #include <algorithm> #include <functional> #include <numeric> #include <utility> #include <sstream> #include <iostream> #include <iomanip> #include <cstdio> #include <cmath> #include <cstdlib> #include <cctype> #include <string> #include <cstring> #include <ctime> #include <queue> using namespace std;
c++では、includeで使用する関数などのヘッダファイルを取り込んで使用します。
中身の実体であるcppファイルはたいてい別にあって、ヘッダファイルは宣言のみを基本的に行うのですが、標準ライブラリはすべてヘッダファイルに実装しているみたいですね。
typedef
//typedef //------------------------------------------ typedef long long LL; typedef vector<int> VI; typedef vector<bool> VB; typedef vector<char> VC; typedef vector<double> VD; typedef vector<LL> VLL; typedef vector<VI> VVI; typedef vector<VB> VVB; typedef vector<string> VS; typedef vector<VLL> VVLL; typedef pair<int, int> PII; typedef pair<LL, LL> PLL; typedef pair<int, string> PIS; typedef pair<string, int> PSI; typedef pair<string, string> PSS;
long longなど、よく使用する型名や、vectorなどはエイリアスをつけています。
正直あまり使用しないもののほうが多いですな･･･
数値・文字列
//数値・文字列
//------------------------------------------
inline int toInt(string s) {
int v;
istringstream sin(s);
sin >> v;
return v;
}
inline LL toLongLong(string s) {
LL v;
istringstream sin(s);
sin >> v;
return v;
}
template<class T>
inline string toString(T x) {
ostringstream sout;
sout << x;
return sout.str();
}
inline VC toVC(string s) {
VC data(s.begin(), s.end());
return data;
}
template<typename List>
void SPRIT(const std::string &s, const std::string &delim, List &result) {
result.clear();
string::size_type pos = 0;
while (pos != string::npos) {
string::size_type p = s.find(delim, pos);
if (p == string::npos) {
result.push_back(s.substr(pos));
break;
} else {
result.push_back(s.substr(pos, p - pos));
}
pos = p + delim.size();
}
}
string TRIM(const string &str, const char *trimCharacterList = " \t\v\r\n") {
string result;
string::size_type left = str.find_first_not_of(trimCharacterList);
if (left != string::npos) {
string::size_type right = str.find_last_not_of(trimCharacterList);
result = str.substr(left, right - left + 1);
}
return result;
}
template<typename T>
bool VECTOR_EXISTS(vector<T> vec, T data) {
auto itr = std::find(vec.begin(), vec.end(), data);
size_t index = distance(vec.begin(), itr);
if (index != vec.size()) {
return true;
} else {
return 0;
}
}
#define UPPER(s) transform((s).begin(), (s).end(), (s).begin(), ::toupper)
#define LOWER(s) transform((s).begin(), (s).end(), (s).begin(), ::tolower)
数が多いので一つ一つ見ていきます。
- toIntは文字列を受け取って数字にして返します。こういうの合ったほうが何かと便利ですね。速度は遅いですが･･･
- toLongLongはtoIntのLL版
- toStringは引数を受け取ってStringにして返します。ostringstreamってなんなんですかね･･･
- toVCは文字列を受け取ってvectorのcharを返します。なんだかんだ変換する必要が多々あるので便利です。
- TRIM関数は文字列をきれいにして返します。ただ、普通の場合入力は整理されているためあまり使いませんね･･･
- VECTOR_EXISTSはテンプレートを使用し、vectorを受け取って特定のdataが存在するかどうかを返します。自分でmain内に書けるレベルですが、読みやすくするためよく使用します。
- UPPERとLOWERは文字列を受け取ってstd::transformで大文字と小文字に変換します。このレベルは普通string型のメソッドにあるべきだと思うんですけど！！！
SPRIT関数はちょっと癖が強いため以下にコードを書いていこうと思います。int main() { string str = "abc def gji"; VS inputs; SPRIT(str, " ", inputs); return 0; }
これはSPRIT関数は３つの引数を受取ります。
第一引数は入力文字
第二引数は文字を分割するためのトークン文字列
第三引数は分割された結果を格納するvector
vectorを使用しているので、何個に分割されるか考える必要がなく、自動で返ってくるので便利ですね･･･
四捨五入
//四捨五入 nLen=小数点第N位にする
//------------------------------------------
//四捨五入
double ceil_n(double dIn, int nLen) {
double dOut;
dOut = dIn * pow(10.0, nLen);
dOut = (double) (int) (dOut + 0.9);
return dOut * pow(10.0, -nLen);
}
//切り捨て
double floor_n(double dIn, int nLen) {
double dOut;
dOut = dIn * pow(10.0, nLen);
dOut = (double) (int) (dOut);
return dOut * pow(10.0, -nLen);
}
//切り上げ
double round_n(double dIn, int nLen) {
double dOut;
dOut = dIn * pow(10.0, nLen);
dOut = (double) (int) (dOut + 0.5);
return dOut * pow(10.0, -nLen);
}
//n桁目の数の取得
int take_a_n(int num, int n) {
string str = toString(num);
return str[str.length() - n] - '0';
}
ceil, floor, round関数の拡張のようです。
自分でもまだ仕組みをよく理解していないため、勉強しようと思います。
標準ライブラリの関数より、小数点以下の桁数を指定できるため細かいです。
take_a_nはそのままです。/=10とかするのが面倒なので文字列にしてから取り出してます。
進数
//進数
//------------------------------------------
//"1111011" → 123
int strbase_2to10(const std::string &s) {
int out = 0;
for (int i = 0, size = s.size(); i < size; ++i) {
out *= 2;
out += ((int) s[i] == 49) ? 1 : 0;
}
return out;
}
//"123" → 1111011
int strbase_10to2(const std::string &s) {
int binary = toInt(s);
int out = 0;
for (int i = 0; binary > 0; i++) {
out = out + (binary % 2) * pow(static_cast<int>(10), i);
binary = binary / 2;
}
return out;
}
//"ABC" 2748
int strbase_16to10(const std::string &s) {
int out = stoi(s, 0, 16);
return out;
}
//1111011 → 123
int intbase_2to10(int in) {
string str = toString(in);
return strbase_2to10(str);
}
//123 → 1111011
int intbase_10to2(int in) {
string str = toString(in);
return strbase_10to2(str);
}
int intbase_16to10(int in) {
string str = toString(in);
return strbase_16to10(str);
}
//123→ "7B"
string intbase_10to16(unsigned int val, bool lower = true) {
if (!val)
return std::string("0");
std::string str;
const char hc = lower ? 'a' : 'A'; // 小文字 or 大文字表記
while (val != 0) {
int d = val & 15; // 16進数一桁を取得
if (d < 10)
str.insert(str.begin(), d + '0'); // 10未満の場合
else // 10以上の場合
str.insert(str.begin(), d - 10 + hc);
val >>= 4;
}
return str;
}
//整数を2進数表記したときの1の個数を返す
LL bitcount64(LL bits) {
bits = (bits & 0x5555555555555555) + (bits >> 1 & 0x5555555555555555);
bits = (bits & 0x3333333333333333) + (bits >> 2 & 0x3333333333333333);
bits = (bits & 0x0f0f0f0f0f0f0f0f) + (bits >> 4 & 0x0f0f0f0f0f0f0f0f);
bits = (bits & 0x00ff00ff00ff00ff) + (bits >> 8 & 0x00ff00ff00ff00ff);
bits = (bits & 0x0000ffff0000ffff) + (bits >> 16 & 0x0000ffff0000ffff);
return (bits & 0x00000000ffffffff) + (bits >> 32 & 0x00000000ffffffff);
}
普通の人は用意してないと思うレベルで用意しています。
TechFULの中級編をやり続けるとこうなります。
ハゲるかと思いました。
strbaseは文字列を受け取ってint型を返します。
intbaseはint型を受け取ってint型を返します。
bitcount64の２進数にしたときの1の個数を数える関数のビット演算の仕組みがよくわかっていないので要学習ですね･･･
比較
//comparison //------------------------------------------ #define C_MAX(a, b) ((a)>(b)?(a):(b)) #define C_MIN(a, b) ((a)<(b)?(a):(b)) #define C_ABS(a, b) ((a)<(b)?(b)-(a):(a)-(b))
c++の標準ライブラリのmin, maxがクソなので使っています。
理由としてはminの片方にlong longなどをぶち込むと反応してくれません。平成アホくさ丸。
ただ、文字列とかぶち込むとC_ABSなどは実行時エラーを吐くので気をつけましょう。
コンテイナー
//container util //------------------------------------------ #define ALL(a) (a).begin(),(a).end() #define RALL(a) (a).rbegin(), (a).rend() #define SZ(a) int((a).size()) #define EACH(i, c) for(typeof((c).begin()) i=(c).begin(); i!=(c).end(); ++i) #define EXIST(s, e) ((s).find(e)!=(s).end()) #define SORT(c) sort((c).begin(),(c).end()) #define RSORT(c) sort((c).rbegin(),(c).rend()) #define REVERSE(c) reverse((c).begin(), (c).end()) #define SUMI(obj) accumulate((obj).begin(), (obj).end(), 0) #define SUMD(obj) accumulate((obj).begin(), (obj).end(), 0.) #define SUML(obj) accumulate((obj).begin(), (obj).end(), 0LL) #define UB(obj, n) upper_bound((obj).begin(), (obj).end(), n) #define LB(obj, n) lower_bound((obj).begin(), (obj).end(), n) #define BS(v, n) binary_search(ALL(v), (n)) #define PB push_back #define MP make_pair
ここらへんは他の方のテンプレートでもよく見ますね･･･小文字派の方もいらっしゃいますが･･･
大体は見ての通りマクロで、vectorなどのSTLをいじるものです。
マクロとか利用したほうが速度だけでなく、ソースコードがかなり読みやすくなりました。
使ってみると、結構欠かせないものになる気がします。
入出力
//input output
//------------------------------------------
#define GL(s) getline(cin, (s))
#define INIT std::ios::sync_with_stdio(false);std::cin.tie(0);
#define OUT(d) std::cout<<(d);
#define OUT_L(d) std::cout<<(d)<<endl;
#define FOUT(n, d) std::cout<<std::fixed<<std::setprecision(n)<<(d);
#define EL() std::cout << "\n";
#define SHOW_VECTOR(v) {std::cerr << #v << "\t:";for(const auto& xxx : v){std::cerr << xxx << " ";}std::cerr << "\n";}
入出力で使用するものです。
- GLはgetlineの略で予め宣言してあったstring変数に一行分格納します。大体使用するときはこのあとSPRIT関数に直結ですね･･･
- INITは入出力がガバガバに多いときは使用します。ただ、これやってギリギリセーフなときは、どこか計算量がガバガバに多い気がします。
- OUT, OUT_Lはcoutの「<<」が面倒なので使用しています。
- FOUTはdouble型の小数を表示するときに、指定桁をnで、表示内容をdで指定することで、○○桁に対応することができます。
- SHOW_VECTORはvector型をぶち込むことでさらっとアサートで表示してくれます。vector型の中身をさらっと確認したいときにデバッグ用で使用してます。
REP
//repetition //------------------------------------------ #define FOR(i, a, b) for(int i=(a);i<(b);++i) #define RFOR(i, a, b) for(int i=(b)-1;i>=(a);--i)å #define REP(i, n) FOR(i,0,n) #define RREP(i, n) for(int i = n;i >= 0;i--) #define FORLL(i, a, b) for(LL i=LL(a);i<LL(b);++i) #define RFORLL(i, a, b) for(LL i=LL(b)-1;i>=LL(a);--i) #define REPLL(i, n) for(LL i=0;i<LL(n);++i) #define RREPLL(i, n) for(LL i=LL(n)-1;i>=0;--i) #define FOREACH(x, v) for(auto &(x) : (v)) #define FORITER(x, v) for(auto (x) = (v).begin(); (x) != (v).end(); ++(x))
これも他の方のテンプレートでもよく見かけますね･･･
大体の内容はこれで書くことができます。
ただ、indexが複雑なときは普通にforで書いたり、正直–iなどのときはRREPで合ってるのか怖いので、forで書いちゃいますね･･･
FOREACHや、FORITERは、STLなどのset,mapなど、indexが扱いづらいものに使用することが多いです。
math
//math
//--------------------------------------------
//min <= aim <= max
template<typename T>
inline bool BETWEEN(const T aim, const T min, const T max) {
if (min <= aim && aim <= max) {
return true;
} else {
return false;
}
}
template<class T>
inline T SQR(const T x) { return x * x; }
template<class T1, class T2>
inline T1 POW(const T1 x, const T2 y) {
if (!y)return 1;
else if ((y & 1) == 0) {
return SQR(POW(x, y >> 1));
} else return POW(x, y ^ 1) * x;
}
template<typename T>
constexpr T ABS(T x) {
static_assert(is_signed<T>::value, "ABS(): argument must be signed");
return x < 0 ? -x : x;
}
//partial_permutation nPr 順列
//first・・最初の数
//middle・・r(取り出す数)
//last・・n(全体数)
template<class BidirectionalIterator>
bool next_partial_permutation(BidirectionalIterator first, BidirectionalIterator middle, BidirectionalIterator last) {
reverse(middle, last);
return next_permutation(first, last);
}
//combination nCr 組み合わせ
//first1・・最初の数
//last1==first2・・r(取り出す数)
//last2・・n(全体数)
template<class BidirectionalIterator>
bool next_combination(BidirectionalIterator first1, BidirectionalIterator last1, BidirectionalIterator first2,
BidirectionalIterator last2) {
if ((first1 == last1) || (first2 == last2)) {
return false;
}
BidirectionalIterator m1 = last1;
BidirectionalIterator m2 = last2;
--m2;
while (--m1 != first1 && !(*m1 < *m2)) {
}
bool result = (m1 == first1) && !(*first1 < *m2);
if (!result) {
while (first2 != m2 && !(*m1 < *first2)) {
++first2;
}
first1 = m1;
std::iter_swap(first1, first2);
++first1;
++first2;
}
if ((first1 != last1) && (first2 != last2)) {
m1 = last1;
m2 = first2;
while ((m1 != first1) && (m2 != last2)) {
std::iter_swap(--m1, m2);
++m2;
}
std::reverse(first1, m1);
std::reverse(first1, last1);
std::reverse(m2, last2);
std::reverse(first2, last2);
}
return !result;
}
ガナリヤの情弱ポイントがバレちゃいますね･･･
数学が苦手なら予め用意していればいいだけの話だ！！！成長はしないが！
- BETWEENはminとmaxの間にデータがあるかboolを返します。TechFULのErrorを避けるのが面倒だったので作りました。
- SQRは二乗です。
- POWはxをy回累乗したものを返します。こういうのはmain内にあるとコードが汚くなるのでありがたいです。標準ライブラリより、型の対応が多いためよく使用します。
- ABSも同様の理由でよく使用します。
- next_partial_permutationはnPrの順列をvector型などで取り出すために使用します。do while(next_permutation())の形で使用するとvector型の要素が自動で変更されていくため便利です。仕組みはよくわかりません
- next_combinationは、標準ライブラリから落選してしまったようなので海外文献から探して使用しています。組み合わせを実現し、do whileで使用します。国内のブログなどには、利用例がないため、ちょっとまだ完璧に使い方が分かりきってはないです･･･
数学法則
//numeric_law
//--------------------------------------------
template<typename T>
constexpr bool ODD(T x) {
return x % 2 != 0;
}
template<typename T>
constexpr bool EVEN(T x) {
return x % 2 == 0;
}
//最大公約数
template<class T>
inline T GCD(const T x, const T y) {
if (x < 0)return GCD(-x, y);
if (y < 0)return GCD(x, -y);
return (!y) ? x : GCD(y, x % y);
}
//最小公倍数
template<class T>
inline T LCM(const T x, const T y) {
if (x < 0)return LCM(-x, y);
if (y < 0)return LCM(x, -y);
return x * (y / GCD(x, y));
}
//ax + by = 1
//x,yが変数に格納される
template<class T>
inline T EXTGCD(const T a, const T b, T &x, T &y) {
if (a < 0) {
T d = EXTGCD(-a, b, x, y);
x = -x;
return d;
}
if (b < 0) {
T d = EXTGCD(a, -b, x, y);
y = -y;
return d;
}
if (!b) {
x = 1;
y = 0;
return a;
} else {
T d = EXTGCD(b, a % b, x, y);
T t = x;
x = y;
y = t - (a / b) * y;
return d;
}
}
//素数
template<class T>
inline bool ISPRIME(const T x) {
if (x <= 1)return false;
for (T i = 2; SQR(i) <= x; i++)if (x % i == 0)return false;
return true;
}
//素数をtrueとして返す
template<class T>
VB ERATOSTHENES(const T n) {
VB arr(n, true);
for (int i = 2; i < SQR(n); i++) {
if (arr[i]) {
for (int j = 0; i * (j + 2) < n; j++) {
arr[i * (j + 2)] = false;
}
}
}
return arr;
}
// a <= x < b の素数を返す
template<typename T>
VB ERATOSTHENES(const T a, const T b) {
VB small = ERATOSTHENES(b);
VB prime(b - a, true);
for (int i = 2; (T) (SQR(i)) < b; i++) {
if (small[i]) {
for (T j = max(2, (a + i - 1) / i) * i; j < b; j += i) {
prime[j - a] = false;
}
}
}
return prime;
}
//約数
template<class T>
vector<T> DIVISOR(T n) {
vector<T> v;
for (int i = 1; i * i <= n; ++i) {
if (n % i == 0) {
v.push_back(i);
if (i != n / i) {
v.push_back(n / i);
}
}
}
sort(v.begin(), v.end());
return v;
}
//組み合わせ個数
template<typename T>
T NCR(T n, T r) {
T ans = 1;
for (T i = n; i > n - r; --i) {
ans = ans * i;
}
for (T i = 1; i < r + 1; ++i) {
ans = ans / i;
}
return ans;
}
//行列
int MATRIZ_CHAIN(VI &p, VVI &s) {
const static int INF = 1 << 20;
const int n = p.size() - 1;
VVI X(n, VI(n, INF));
s.resize(n, VI(n));
for (int i = 0; i < n; ++i) X[i][i] = 0;
for (int w = 1; w < n; ++w)
for (int i = 0, j; j = i + w, j < n; ++i)
for (int k = i; k < j; ++k) {
int f = p[i] * p[k + 1] * p[j + 1];
if (X[i][k] + X[k + 1][j] + f < X[i][j]) {
X[i][j] = X[i][k] + X[k + 1][j] + f;
s[i][j] = k;
}
}
return X[0][n - 1];
}
//最長増加部分列
VI LIS(const VI &a) {
const static int INF = 99999999;
const int n = a.size();
VI A(n, INF);
VI id(n);
for (int i = 0; i < n; ++i) {
id[i] = distance(A.begin(), lower_bound(A.begin(), A.end(), a[i]));
A[id[i]] = a[i];
}
int m = *max_element(id.begin(), id.end());
VI b(m + 1);
for (int i = n - 1; i >= 0; --i)
if (id[i] == m) b[m--] = a[i];
return b;
}
//最長共通部分列 string->toVC
template<typename T>
vector<T> LCS(const vector<T> &a, const vector<T> &b) {
const int n = a.size(), m = b.size();
vector<VI> X(n + 1, VI(m + 1));
vector<VI> Y(n + 1, VI(m + 1));
REP(i, n) {
REP(j, m) {
if (a[i] == b[j]) {
X[i + 1][j + 1] = X[i][j] + 1;
Y[i + 1][j + 1] = 0;
} else if (X[i + 1][j] < X[i][j + 1]) {
X[i + 1][j + 1] = X[i][j + 1];
Y[i + 1][j + 1] = +1;
} else {
X[i + 1][j + 1] = X[i + 1][j];
Y[i + 1][j + 1] = -1;
}
}
}
vector<T> c;
for (int i = n, j = m; i > 0 && j > 0;) {
if (Y[i][j] > 0) --i;
else if (Y[i][j] < 0) --j;
else {
c.PB(a[i - 1]);
--i;
--j;
}
}
REVERSE(c);
return c;
}
//コイン C総額 cs使用できるコインの種類
VI money_change(int C, VI &cs) {
const int INF = 99999999;
int n = cs.size();
VI xs(C + 1, INF);
VI ys(C + 1);
xs[0] = 0;
for (int i = 0; i < n; ++i) {
for (int c = 0; c + cs[i] <= C; ++c) {
if (xs[c + cs[i]] > xs[c] + 1) {
xs[c + cs[i]] = xs[c] + 1;
ys[c + cs[i]] = c;
}
}
}
VI zs;
for (int c = C; c > 0; c = ys[c]) {
zs.push_back(c - ys[c]);
}
return zs;
}
長すぎぃ！
でも合ったほうが便利だからええやろ(甘え)
- ODDは奇数かどうか判定します。inlineをつけてないのでつけようかと思います。
- GCDは引数x, yの最大公約数を算出します。ユークリッドの互除法をしています。
- LCMは最小公倍数を算出します。ab = GCD(a,b)*LCM(a,b)という法則があるため、GCDで算出した答えを利用してLCMを算出します。
- EXTGCDはax+by=1となるx,yが格納されます。仕組みがまだ良くわかってないです。
- ISPRIMEは引数が素数かどうか判定します。一つの数字のみでいいならこちらを使います。
- ERATOSTHENESは素数のふるいを行います。配列に格納しておいて、素数を見つけるとSQR(n)分まで回すことで素数以外をfalseにすることで早く計算できます。
- DIVISORは約数を算出してvectorにして返します。n*nのsqrt以内に半分の素数は存在するため、そちらで算出し、i!=n/iで反対側の素数を算出しています。
- NCRはnCrの意味で組み合わせを算出します。ただいま、先にかけ算を行っており、数がおおきいとオーバーフローしてしまうため、改善が必要かもしれませんね。
- LISは部分増加列を算出します。ここらへんはよく出るので、どんな仕組みだったからって確認するために記述させていただいてます。
- LCSは二つの文字列の部分増加列です。もはや辞書的な役割です。
confirmation
//confirmation //-------------------------------------------- //clear memory #define CLR(a, b) memset((a), (b),sizeof(a)) //debug #define dump(x) cerr << #x << " = " << (x) << endl; #define debug(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ")" << " " << __FILE__ << endl;
メモリーの初期化(配列に限る)や、デバッグで使用するマクロです。
fillをまだマクロで定義してないのでfillも実装しとこうと思います。
あ〜すっげぇキツかったぞ〜
自分が以下にライブラリに頼っているかがバレましたね･･･（バレてるんだよなぁ･･･）
マクロを使うと結構楽に、はやく書けますし、よくわからん数学の部分をオーバーラップできます。
自分なりのテンプレートを作って競プロやると、結構楽しいかもしれません。
僕は、結構使えそうなマクロ作ったり探したりする時間が、競プロの中で一番好きです。（こんな人間になってはいけない）
P.S.
かえみと尊い･･･尊くない･･･？