---
tags: 競プロ
---
# あまり知られていない〈algorithm〉
この記事は [Competitive Programming (1) Advent Calendar 2020](https://adventar.org/calendars/4969) 6 日目の記事です。
昨日の記事はわくさんの [競技プログラミングの作問環境構築（gitとrime編）](https://wakuwinmail.hatenablog.com/entry/2020/12/05/015747) でした。
---
C++ の標準ライブラリには便利な関数がたくさんあります。 特に [<algorithm>](https://cpprefjp.github.io/reference/algorithm) と [<numeric>](https://cpprefjp.github.io/reference/numeric) には便利な関数が多いので、その紹介をしようという記事です。
<span style="font-size: 200%">C++ 使いは cpprefjp を読もう！</span>
## よく使われているやつ
- [`find`](https://cpprefjp.github.io/reference/algorithm/find.html)
指定した値を見つけてくる
- [`count`](https://cpprefjp.github.io/reference/algorithm/count.html)
指定した値を数える
- [`fill`](https://cpprefjp.github.io/reference/algorithm/fill.html)
指定した値を代入する
- [`unique`](https://cpprefjp.github.io/reference/algorithm/unique.html)
重複をなくす
- [`reverse`](https://cpprefjp.github.io/reference/algorithm/reverse.html)
ひっくり返す
- [`shuffle`](https://cpprefjp.github.io/reference/algorithm/shuffle.html)
シャッフルする
- [`sort`](https://cpprefjp.github.io/reference/algorithm/sort.html)
ソートする
- [`lower_bound`](https://cpprefjp.github.io/reference/algorithm/lower_bound.html)
二分探索する
- [`upper_bound`](https://cpprefjp.github.io/reference/algorithm/upper_bound.html)
二分探索する
- [`min`](https://cpprefjp.github.io/reference/algorithm/min.html)
最小値を返す
- [`max`](https://cpprefjp.github.io/reference/algorithm/max.html)
最大値を返す
- [`min_element`](https://cpprefjp.github.io/reference/algorithm/min_element.html)
最小値のイテレータを返す
- [`max_element`](https://cpprefjp.github.io/reference/algorithm/max_element.html)
最大値のイテレータを返す
- [`next_permutation`](https://cpprefjp.github.io/reference/algorithm/next_permutation.html)
次の順列を作る
など
## 全て / いずれかの要素が条件を満たすか調べたい時
- [`all_of`](https://cpprefjp.github.io/reference/algorithm/all_of.html)
- [`any_of`](https://cpprefjp.github.io/reference/algorithm/any_of.html)
- [`none_of`](https://cpprefjp.github.io/reference/algorithm/none_of.html)
[ABC155-B Papers, Please](https://atcoder.jp/contests/abc155/tasks/abc155_b)
```cpp
if(all_of(A.begin(), A.end(), [](int x){ return x % 2 || x % 3 == 0 || x % 5 == 0; }))
puts("APPROVED");
else puts("DENIED");
```
flag を持って、 for 文回して、そのあと if 文を書かないといけなかったのが全部 if 文の中に収まる。 えらい。
## 条件を満たすものの個数を数えたい時
- [`count_if`](https://cpprefjp.github.io/reference/algorithm/count_if.html)
[ABC182-B Almost GCD](https://atcoder.jp/contests/abc182/tasks/abc182_b)
```cpp
int ans, max = 0;
for(int k = 2; k <= 1000; k++){
if(chmax(max, count_if(A.begin(), A.end(), [k](int x){ return x % k == 0; })))
ans = k;
}
cout << ans << endl;
```
## 変換して総和を取りたいとき
- [`transform_reduce`](https://cpprefjp.github.io/reference/numeric/transform_reduce.html)
[ABC180-B Various distances](https://atcoder.jp/contests/abc180/tasks/abc180_b)
```cpp
long D1 = transform_reduce(x.begin(), x.end(), 0L, plus{}, abs<long>);
long D2 = transform_reduce(x.begin(), x.end(), 0L, plus{}, bind(multiplies{}, placeholders::_1, placeholders::_1));
long D3 = transform_reduce(x.begin(), x.end(), 0L, [](long a, long b){ return max(a, b); }, abs<long>);
// const T& max(const T&, const T&) と const T& max(initializer_list<T>) の 2 種類あるので max<long> とはできない
cout << D1 << endl;
cout << sqrt(D2) << endl;
cout << D3 << endl;
```
#### `plus{}` って何？
[関数オブジェクト](https://cpprefjp.github.io/reference/functional.html) というやつ
基本的には
```cpp
template<class T> struct plus{
T operator()(T a, T b){ return a + b; }
};
```
のようなものだと思っておくと良い
`+` などの演算子はたいてい関数ポインタとして渡せないため、その代わりのもの
`plus<int> p;` でオブジェクトを作り、 `p(1, 2)` のように関数適用できる
#### `bind` って何？
- [`bind`](https://cpprefjp.github.io/reference/functional/bind.html)
引数に定数を固定したり、複数の引数を 1 つにまとめた関数オブジェクトを生成できる
利用例 :
`bind(uniform_int_distribution(1, 100), rng)` で [`uniform_int_distribution`](https://cpprefjp.github.io/reference/random/uniform_int_distribution.html) に乱数生成機を固定できる
## ハミング距離を求めたい時
2 つの列を変換して総和を取りたいときも [`transform_reduce`](https://cpprefjp.github.io/reference/numeric/transform_reduce.html) でできるんですね〜
[ABC177-B Substring](https://atcoder.jp/contests/abc177/tasks/abc177_b)
```cpp
int ans = INF;
for(auto p = S.begin(); S.end() - p >= T.size(); p++){
chmin(ans, transform_reduce(T.begin(), T.end(), p, 0, plus{}, not_equal_to{}));
}
cout << ans << endl;
```
#### ちなみに
[`inner_product`](https://cpprefjp.github.io/reference/numeric/inner_product.html) のほうが 3 文字短い
## for 文を使わずに配列に入力する
- [`istream_iterator`](https://cpprefjp.github.io/reference/iterator/istream_iterator.html)
- [`copy_n`](https://cpprefjp.github.io/reference/algorithm/copy_n.html)
```cpp
vector<int> a(n);
copy_n(istream_iterator<int>(cin), n, a.begin());
```
[`istream_iterator`](https://cpprefjp.github.io/reference/iterator/istream_iterator.html) は `istream` から入力した結果を返してくれるイテレータ
`auto p = istream_iterator<int>(cin)` とすると、
`*p` で現在の `cin` の位置から整数 1 個を読んだ時の値を返す
`p++` で `cin` を整数 1 個分進める
ことができる
## 累積和をとりたいとき
- [`exclusive_scan`](https://cpprefjp.github.io/reference/numeric/exclusive_scan.html)
```cpp
vector<int> A = {1, 2, 3, 4};
A.push_back(0);
exclusive_scan(A.begin(), A.end(), A.begin());
// A == {0, 1, 3, 6, 10}
```
## 累積和の逆操作をしたいとき
- [`adjacent_difference`](https://cpprefjp.github.io/reference/numeric/adjacent_difference.html)
```cpp
vector<int> A = {0, 1, 3, 6, 10}, B(5);
adjacent_difference(A.begin(), A.end(), B.begin());
// B == {0, 1, 2, 3, 4}
```
#### ちなみに
隣接 2 要素に対して何かを計算したい時にも使える
## 回文かどうか判定したい時
- [`equal`](https://cpprefjp.github.io/reference/algorithm/equal.html)
```cpp
bool palindrome(const string& s){
return equal(s.begin(), s.end(), s.rbegin());
}
```
## 条件を満たすもの全てを削除したい時
[`vector::erase_if`](https://cpprefjp.github.io/reference/vector/vector/erase_if_free.html) は残念ながら C++20 から
代わりに [`remove_if`](https://cpprefjp.github.io/reference/algorithm/remove_if.html) を使う
```cpp
vector<int> A = {0, 1, 3, 0, 5, 0};
A.erase(remove_if(A.begin(), A.end(), logical_not{}), A.end());
// A == {1, 3, 5}
```
## 配列の要素をずらしたいとき
- [`rotate`](https://cpprefjp.github.io/reference/algorithm/rotate.html)
利用例 : 前半と後半を入れ替える
https://codeforces.com/contest/1381/submission/87563323
```cpp
vector<int> A = {0, 1, 2, 3, 4};
rotate(A.begin(), A.begin() + A.size() / 2, A.end());
// A == {2, 3, 4, 0, 1}
```
## おわりに
言語仕様を把握して実装力を上げよう！
明日は Hyado さんが変なmodについて書くようです！楽しみ〜
<div style="font-size:20%">
MMNMM さんがどこかの問題で `next_permutation` と `inner_product` を使ってめちゃくちゃ賢い実装をしていた記憶があるんですが、どこにあるでしょうか……
</div>
Sign in with Wallet
Connect another wallet