Posted at

競技プログラミングで使えるBoostライブラリ 初級編


競技プログラミングで使えるBoostライブラリ 初級編


はじめに

AtCoderではC++のBoostライブラリを使用することができます。

Boostライブラリには非常に多くの機能がありますが、そのうち便利だなと思ったものを簡単に紹介します。


boost::irange

ABC072B - OddString


ABC072B

#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

ABC059B - Comparison


ABC059B

#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

ABC033C - 数式の書き換え


ABC033C.cpp

#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)


ABC042B.cpp

#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

ARC045A - スペース高橋君


ARC45.cpp

#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

ARC54B - ムーアの法則


ARC54B.cpp

#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.firstr.secondで得られます。


まとめ

いかがだったでしょうか。

競技プログラミングの問題を例として、Boostライブラリの便利な機能の一部を紹介できたかなと思います。

もっと便利な書き方もあるよ、などのコメントもいただけると嬉しいです!