HackMD
あまり知られていない〈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
次の順列を作る
など
全て / いずれかの要素が条件を満たすか調べたい時
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 文の中に収まる。 えらい。
条件を満たすものの個数を数えたい時
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;
変換して総和を取りたいとき
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 って何？
引数に定数を固定したり、複数の引数を 1 つにまとめた関数オブジェクトを生成できる
利用例 :
bind(uniform_int_distribution(1, 100), rng) で uniform_int_distribution に乱数生成機を固定できる
ハミング距離を求めたい時
2 つの列を変換して総和を取りたいときも transform_reduce でできるんですね〜
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 文を使わずに配列に入力する
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 個分進める
ことができる
累積和をとりたいとき
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}
累積和の逆操作をしたいとき
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 要素に対して何かを計算したい時にも使える
回文かどうか判定したい時
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}
配列の要素をずらしたいとき
利用例 : 前半と後半を入れ替える
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 を使ってめちゃくちゃ賢い実装をしていた記憶があるんですが、どこにあるでしょうか……
