競プロで使っている便利関数メモ(C++)

# 概要
趣味の競プロで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

# 参考文献
- 入門・学習サイト
  - [C++入門 AtCoder Programming Guide for beginners (APG4b)](https://atcoder.jp/contests/APG4b)
- 書籍
  - [第2版 プログラミングコンテスト チャレンジブック](https://www.amazon.co.jp/%E3%83%97%E3%83%AD%E3%82%B0%E3%83%A9%E3%83%9F%E3%83%B3%E3%82%B0%E3%82%B3%E3%83%B3%E3%83%86%E3%82%B9%E3%83%88%E3%83%81%E3%83%A3%E3%83%AC%E3%83%B3%E3%82%B8%E3%83%96%E3%83%83%E3%82%AF-%E7%AC%AC2%E7%89%88-%EF%BD%9E%E5%95%8F%E9%A1%8C%E8%A7%A3%E6%B1%BA%E3%81%AE%E3%82%A2%E3%83%AB%E3%82%B4%E3%83%AA%E3%82%BA%E3%83%A0%E6%B4%BB%E7%94%A8%E5%8A%9B%E3%81%A8%E3%82%B3%E3%83%BC%E3%83%87%E3%82%A3%E3%83%B3%E3%82%B0%E3%83%86%E3%82%AF%E3%83%8B%E3%83%83%E3%82%AF%E3%82%92%E9%8D%9B%E3%81%88%E3%82%8B%EF%BD%9E-%E7%A7%8B%E8%91%89%E6%8B%93%E5%93%89/dp/4839941068) (通称:蟻本)
- Qiita
  - [AtCoder に登録したら次にやること ～ これだけ解けば十分闘える！過去問精選 10 問 ～](https://qiita.com/drken/items/fd4e5e3630d0f5859067)
  - [「1000000007 で割ったあまり」の求め方を総特集！ 〜 逆元から離散対数まで 〜](https://qiita.com/drken/items/3b4fdf0a78e7a138cd9a)