競技プログラミングで使える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.firstとr.secondで得られます。

###まとめ

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

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