競技プログラミングで使えるBoostライブラリ 初級編
はじめに
AtCoderではC++のBoostライブラリを使用することができます。
Boostライブラリには非常に多くの機能がありますが、そのうち便利だなと思ったものを簡単に紹介します。
boost::irange
#include <bits/stdc++.h>
#include <boost/range/irange.hpp>
using namespace std;
using boost::irange;
int main() {
string s;
cin >> s;
int n = s.size();
for (int i : irange(0, n, 2)) {
cout << s[i];
}
cout << endl;
}
整数のレンジを使うにはboost::irange関数を使います。
範囲として[0, n)を指定して、第3引数でステップ幅を2に指定しています。
(第3引数を省略するとステップ幅は1になります)
これに対してrange-based for文を記述することができ、Pythonのfor文と近い感覚になります。
boost::multiprecision::cpp_int
#include <bits/stdc++.h>
#include <boost/multiprecision/cpp_int.hpp>
using namespace std;
using boost::multiprecision::cpp_int;
int main() {
cpp_int a, b;
cin >> a >> b;
cout << (a > b ? "GREATER" : (a == b ? "EQUAL" : "LESS")) << endl;
}
多倍長整数を扱うにはboost::multiprecision::cpp_intを使います。
この問題で与えられる整数は$10^{100}$以下という制限となっており、数値として扱うために多倍長整数で受け取っています。
boost::algorithm::split
#include <bits/stdc++.h>
#include <boost/algorithm/string/classification.hpp> // is_any_of
#include <boost/algorithm/string/split.hpp>
using namespace std;
using boost::algorithm::split;
int main() {
string s;
cin >> s;
vector<string> plus_split_s;
split(plus_split_s, s, boost::is_any_of("+"));
int cnt = 0;
for (const string& elem : plus_split_s) {
if (elem.find('0') == string::npos) ++cnt;
}
cout << cnt << endl;
}
指定した区切り文字で文字列を分割するにはboost::algorithm::split関数を使用します。
得られた結果は指定したコンテナで受け取ります。
区切り文字かどうかを判定する述語としてboost::is_any_ofを使用しています。
今回の例では文字列を+で区切っています。以下のように記述してもよいです。
split(plus_split_s, s, [](char c){return c == '+';});
boost::algorithm::join
ABC042B - 文字列大好きいろはちゃんイージー / Iroha Loves Strings (ABC Edition)
#include <bits/stdc++.h>
#include <boost/algorithm/string/join.hpp>
using namespace std;
using boost::algorithm::join;
int main() {
int n, l;
cin >> n >> l;
vector<string> arr(n);
for (int i = 0; i < n; ++i) {
cin >> arr[i];
}
sort(arr.begin(), arr.end());
string s = join(arr, "");
cout << s << endl;
}
コンテナの文字列をつなげて一つの文字列にするには、boost::algorithm::join関数を使用します。
つなげる区切り文字を指定でき、例えば以下のように記述すれば_で区切られた文字列になります。
string s = join(arr, "_");
boost::algorithm::replace_all
#include <bits/stdc++.h>
#include <boost/algorithm/string/replace.hpp>
using namespace std;
using boost::algorithm::replace_all;
int main() {
string s;
getline(cin, s);
replace_all(s, "Left", "<");
replace_all(s, "Right", ">");
replace_all(s, "AtCoder", "A");
cout << s << endl;
}
文字列の中の要素をすべて別の要素に置き換えるにはboost::algorithm::replace_all関数を使用します。
これは破壊的処理であり、もともとの文字列sを変更しています。
非破壊的にコピーを作って置換する場合はboost::algorithm::replace_all_copy関数を使えばよいです。
例えば以下のように書きます。
string result = boost::algorithm::replace_all_copy(s, "AtCoder", "A");
boost::math:: tools::brent_find_minima
#include <bits/stdc++.h>
#include <boost/math/tools/minima.hpp>
using namespace std;
using boost::math::tools::brent_find_minima;
int main() {
double p;
cin >> p;
auto r = brent_find_minima([p](double x) {return x + p / pow(2.0 , x / 1.5);}, 0.0, 100.0, 30);
cout << fixed << setprecision(15);
cout << r.second << endl;
}
関数の最小値を探索するにはboost::math::tools::brent_find_minima関数を使用します。
今回の例では関数をラムダ式で記述し、xの探索範囲を指定しています。
結果をrに代入しています。最小値となるxの値と関数の値が、それぞれr.firstとr.secondで得られます。
まとめ
いかがだったでしょうか。
競技プログラミングの問題を例として、Boostライブラリの便利な機能の一部を紹介できたかなと思います。
もっと便利な書き方もあるよ、などのコメントもいただけると嬉しいです！