概要
趣味の競プロでC++を使ってます。
それまではC++を使ったことがなかったので解答方針を思いついても、実装に戸惑うことが多々ありました。
都度便利関数を作ってましたが、ある程度溜まったのでご紹介します。
折角なのでJavaDocチックに記載してみました。英語変ならご指摘ください。
対象者
- 競プロ始めるよーって方
- 最近競プロ始めた方
文字修飾
基本操作
大文字、小文字変換と、splitです。
cppにsplitないんですよね。。
string.cpp
/**
* Return upper string.
*
* eg. toUpper("AbcD") -> "ABCD"
* @param s The string you want to convert.
* @return UPPER string
*/
string toUpper(string s){
transform(s.cbegin(), s.cend(), s.begin(), ::toupper);
return s;
}
/**
* Return lower string.
*
* eg. toLower("AbcD") -> "abcd"
* @param s The string you want to convert.
* @return lower string
*/
string toLower(string s){
transform(s.cbegin(), s.cend(), s.begin(), ::tolower);
return s;
}
/**
* Return array of strings separated by the delimiter specified by the second argument.
*
* eg. split("ab|cd|e|f", '|') -> ["ab","cd","e","f"]
* eg. split("|ab|cd|e|f|", '|') -> ["ab","cd","e","f"]
* @param s The string you want to convert.
* @param delim The character you want to separate.
* @return The array of strings after separated.
*/
vector<string> split(string s, char delim){
int startIdx = 0;
int len = 0;
vector<string> ret;
for (int i = 0; i < (int)s.size(); i++) {
if(s[i] == delim){
if (len != 0) ret.push_back(s.substr(startIdx, len));
startIdx = i+1;
len = 0;
} else {
len++;
}
}
if (len != 0) ret.push_back(s.substr(startIdx, len));
return ret;
}
deque<char> / deque<string>
（この部分はメモのみ）
文字を継ぎ足ししていくBuilder的処理は、stringの足し算では遅くなる（理由は割愛）。
dequeで溜めて扱うことが多い。特に回分作成。
その他（標準で提供される関数メモ）
stringStls.cpp
int memo() {
// string -> int
cout << stoi("100") << endl;
// int -> string
cout << to_string(100) << endl;
// Repeat the same character.
cout << string(5, 'a') << endl; // -> "aaaaa"
}
数値計算
素数
素数判定、約数列挙、素因数分解を用意してます。
primeCalc.cpp
/**
* Judgement prime or not.
*
* @return bool When prime, return true.
*/
template<typename T>
bool isPrime(T n) {
for (T i = 2; i*i <= n; i++) {
if (n%i == 0) return false;
}
return n != 1;
}
/**
* Return array of divisors.
*
* eg. arrangeDivisor(12) -> [1, 12, 2, 6, 3, 4]
*/
template<typename T>
vector<T> arrangeDivisor(T n) {
vector<T> ret;
for (T i = 1; i*i <= n; i++) {
if (n%i == 0) {
ret.push_back(i);
if (i != n/i) ret.push_back(n/i);
}
}
return ret;
}
/**
* Return result of prime factorization.
*
* eg. primeFactorize(30) -> [{2,2},{3,1},{5,1}]
* @return map<T, int> prime, count
*/
template<typename T>
map<T, int> primeFactorize(T n) {
map<T, int> ret;
for (T i = 2; i*i <= n; i++) {
while (n%i == 0) {
ret[i]++;
n /= i;
}
}
if (n != 1) ret[n] = 1;
return ret;
}
mod計算
競プロでよくある「1000000007 で割った余り」を計算に使います。
引き算、累乗、割り算（素数で割るとき限定）、コンビネーション（素数で割るとき限定）を用意してます。
modCalc.cpp
/**
* Return the Modulo result after subtraction.
*
* When the subtraction result becomes negative, add modulo value in order to be always positive.
* eg. modMinus(5, 1, 10) -> 4(=(5-3)%10)
* eg. modMinus(1, 5, 10) -> 6(=(10+(3-5))%10)
*/
template <typename T>
T modMinus(T a, T b, T mod) {
a %= mod;
b %= mod;
return (a>b)? (a-b)%mod: (mod+a-b)%mod;
}
/**
* Return the Modulo result after power calculation.
*
* Implemented by the division-and-conquer method which is fast algorithm.
* eg. modPow(2, 3, 10) -> 8(=(2*2*2)%10)
* eg. modPow(2, 4, 10) -> 6(=(2*2*2*2)%10)
*/
template <typename T>
T modPow(T base, T e, T mod) {
if(e == 0) return 1;
if(e == 1) return base%mod;
if(e%(T)2 == 1) return (base * modPow(base, e-(T)1, mod)) %mod;
T tmp = modPow(base, e/(T)2, mod);
return (tmp * tmp) % mod;
}
/**
* Return the Modulo result after division.
*
* The dividing value must be a prime number because the inverse element is used.
* In other words, this function uses Fermat's little theorem.
*/
template <typename T>
T primeModDiv(T num, T den, T primeMod){
return ( num*modPow(den, primeMod-(T)2, primeMod) )%primeMod;
}
/**
* Return the Modulo of binomial coefficients (Value of n-C-k %mod).
*
* The dividing value must be a prime number because the inverse element is used.
* In other words, this function uses Fermat's little theorem.
*/
template <typename T>
T modComb(T n, T k, T mod) {
T num = (T)1; //numerator
T den = (T)1; //denominator
for (T i = 1; i <= k; i++) {
num *= (n-i+(T)1);
num %= mod;
den *= i;
den %= mod;
}
return primeModDiv(num, den, mod);
}
最小公倍数、最大公約数
gcdAndLcm.cpp
/**
* Return greatest common divisor.
*/
template <typename T>
T gcd(T a, T b) {
if (a%b == 0) return b;
return gcd(b, a%b);
}
/**
* Return least common multiple.
*/
template <typename T>
T lcm(T a, T b) {
return (a / gcd(a, b)) * b ;
}
その他
a/b の計算で、丁度割り切れたらそのままで、余りがあったら+1したい、そんなときは、(a-1)/b + 1 という式で条件分岐なしで実装できます。
Output
output.cpp
//浮動小数の型の出力時に小数桁の表示精度を指定。
//cout<<fixed<<setprecision(6)を実行しておく。
cout<<fixed<<setprecision(6)<<double(1.0)<<endl; // -> 1.000000
//bit表示
cout << bitset<3>(1) << endl; // -> 001
cout << bitset<3>(2) << endl; // -> 010
cout << bitset<3>(3) << endl; // -> 011
cout << bitset<3>(4) << endl; // -> 100
cout << bitset<3>(5) << endl; // -> 101
set, multisetの操作
set, multisetの便利関数を作った理由
setとmultiset（mapもですが）内部でデータをソートして保持しているため、最初の値を参照すれば最小値を、最後の値を参照すれば最大値を取得できます（計算量O(1)）。
最初の値や、最後の値を参照するにはbegin()やrbegin()を使えばいいのですが、オブジェクトが空のときはエラーになります。空のときの分岐がめんどくさいのでメソッドにしました。オブジェクトが空のときは第2引数の値を返すようにしてるので呼び出し側でよしなに扱ってください。
また、multisetの標準のerase()は引数で指定した値にヒットした要素をすべて消す仕様のため、1つだけ消したい場合に困ります。このため、eraseOne()というメソッドを作りました。
erase.cpp
//multisetのeraseメソッドの挙動説明用です。これは便利関数ではないです。
int sample(){
multiset<int> ms = {1,2,2,3};
for (auto v: ms) cout << v << " "; // 1 2 2 3
cout << endl;
ms.erase(2);
for (auto v: ms) cout << v << " "; // 1 3
cout << endl;
}
multiset
multiset.cpp
/**
* Return minimum value in the first argument.
*
* When object is empty, return the value specified by the second argument.
*/
template<typename T>
T minValue(multiset<T>& ms, T emptyValue) {
if (ms.empty()) return emptyValue;
return *ms.begin();
}
/**
* Return maximum value in the first argument.
*
* When object is empty, return the value specified by the second argument.
*/
template<typename T>
T maxValue(multiset<T>& ms, T emptyValue) {
if (ms.empty()) return emptyValue;
return *ms.rbegin();
}
/**
* Erase one element of the value specified by the second argument from the first argument.
*
* Only one element is erased, even when there are multiple elements with the specified value.
* But when the element not found, do nothing.
*/
template<typename T>
void eraseOne(multiset<T>& ms, T eraseValue) {
auto itr = ms.find(eraseValue);
if (itr!=ms.end()){
ms.erase(itr);
}
return;
}
set
set.cpp
/**
* Return minimum value in the first argument.
* When object is empty, return the value specified by the second argument.
*/
template<typename T>
T minValue(set<T>& ms, T emptyValue) {
if (ms.empty()) return emptyValue;
return *ms.begin();
}
/**
* Return maximum value in the first argument.
* When object is empty, return the value specified by the second argument.
*/
template<typename T>
T maxValue(set<T>& ms, T emptyValue) {
if (ms.empty()) return emptyValue;
return *ms.rbegin();
}
二分探索（めぐる式）
これです。勉強になります。
https://twitter.com/meguru_comp/status/697008509376835584