あまり知られていない〈algorithm〉

この記事は Competitive Programming (1) Advent Calendar 2020 6 日目の記事です。

昨日の記事はわくさんの 競技プログラミングの作問環境構築（gitとrime編） でした。

---

C++ の標準ライブラリには便利な関数がたくさんあります。 特に <algorithm> と <numeric> には便利な関数が多いので、その紹介をしようという記事です。

C++ 使いは cpprefjp を読もう！

よく使われているやつ

• find
  指定した値を見つけてくる
• count
  指定した値を数える
• fill
  指定した値を代入する
• unique
  重複をなくす
• reverse
  ひっくり返す
• shuffle
  シャッフルする
• sort
  ソートする
• lower_bound
  二分探索する
• upper_bound
  二分探索する
• min
  最小値を返す
• max
  最大値を返す
• min_element
  最小値のイテレータを返す
• max_element
  最大値のイテレータを返す
• next_permutation
  次の順列を作る

など

全て / いずれかの要素が条件を満たすか調べたい時

• all_of
• any_of
• none_of

ABC155-B Papers, Please

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

ABC182-B Almost GCD

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

ABC180-B Various distances

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{} って何？

関数オブジェクト というやつ

基本的には

template<class T> struct plus{
    T operator()(T a, T b){ return a + b; }
};

のようなものだと思っておくと良い

+ などの演算子はたいてい関数ポインタとして渡せないため、その代わりのもの
plus<int> p; でオブジェクトを作り、 p(1, 2) のように関数適用できる

bind って何？

• bind

引数に定数を固定したり、複数の引数を 1 つにまとめた関数オブジェクトを生成できる

利用例 :
bind(uniform_int_distribution(1, 100), rng) で uniform_int_distribution に乱数生成機を固定できる

ハミング距離を求めたい時

2 つの列を変換して総和を取りたいときも transform_reduce でできるんですね〜

ABC177-B Substring

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 のほうが 3 文字短い

for 文を使わずに配列に入力する

• istream_iterator
• copy_n

vector<int> a(n);
copy_n(istream_iterator<int>(cin), n, a.begin());

istream_iterator は istream から入力した結果を返してくれるイテレータ
auto p = istream_iterator<int>(cin) とすると、
*p で現在の cin の位置から整数 1 個を読んだ時の値を返す
p++ で cin を整数 1 個分進める
ことができる

累積和をとりたいとき

• exclusive_scan

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

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

bool palindrome(const string& s){
    return equal(s.begin(), s.end(), s.rbegin());
}

条件を満たすもの全てを削除したい時

vector::erase_if は残念ながら C++20 から

代わりに remove_if を使う

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://codeforces.com/contest/1381/submission/87563323

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について書くようです！楽しみ〜

MMNMM さんがどこかの問題で next_permutation と inner_product を使ってめちゃくちゃ賢い実装をしていた記憶があるんですが、どこにあるでしょうか……